NPではなく、NPの問題があり、NPが完了していませんか？

Question

$ mathsf {np} $（$ mathsf {p} $ではない）に既知の問題はありますか？私の理解では、これが事実であることが現在知られている問題はありませんが、可能性として除外されていません。

$ mathsf {np} $である問題があるが、$ mathsf {np text { - } complete} $ではないが、これは既存の同型の結果ではないでしょうかその問題のインスタンスと$ mathsf {np text { - } complete} $ setの間？この場合、$ mathsf {np} $の問題は、$ mathsf {np text { - } complete} $ setとして現在識別しているものよりも「難しくない」ことをどのように知るでしょうか？

Answer 1

NPが完了していないNP（Pではない）で既知の問題はありますか？私の理解では、これが事実であることが現在知られている問題はありませんが、可能性として除外されていません。

いいえ、これは不明です（些細な言語$ emptySet $と$ sigma^*$を除き、これら2つは多くの1つの削減の定義のために完全ではありません。削減）。 $ mathsf {np} $の問題の存在$ mathsf {np} $ wrt多項式時間削減は、$ mathsf {p} neq mathsf {np} $を意味します。既知（広く信じられているが）。 2つのクラスが異なる場合、$ mathsf {np} $には問題があることがわかります。

NPではなく、NPが完了していない問題がある場合、これはその問題のインスタンスとNP完全セットの間に既存の同型がありませんか？

2つの複雑なクラスが異なる場合 ラドナーの定理 $ mathsf {np} $ - 中間、つまり$ mathsf {p} $と$ mathsf {np text { - } complete} $の問題があります。

この場合、NPの問題が現在NPの完全なセットとして識別されているものよりも「難しい」ことをどのように知るでしょうか？

それらはまだ$ mathsf {np text { - } complete} $の問題に還元可能であるため、$ mathsf {np text { - } complete} $の問題よりも難しくなりません。

Answer 2

@kavehが述べたように、この質問は$ p neq np $を想定した場合にのみ興味深いものです。私の答えの残りの部分は、これを仮定として受け取り、主にあなたの食欲をさらに濡らすためのリンクを提供します。その仮定の下で、Ladnerの定理によって、$ P $も$ npc $も存在しない問題があることを知っています。これらの問題は、$ np $ intermediateまたは$ npi $と呼ばれます。興味深いことに、ラドナーの定理は一般化できます 他の多くの複雑なクラス 同様の中間問題を生成する。さらに、定理は、 無限の階層 $ npi $で互いに削減できない中間の問題の。

残念ながら、仮定$ p neq np $を使用しても、$ npi $である自然な問題を見つけることは非常に困難です（もちろん、Ladnerの定理の証明から人為的な問題があります）。したがって、この時点で$ p neq np $を想定しても、$ npi $であるとは信じられないが、それを証明しないと信じることができます。 $ np $の問題が$ npc $にないか、$ p $ではないと信じる合理的な証拠がある場合、私たちはそのような信念に至ります。または、それが長い間研究されており、どちらのクラスにもフィッティングを避けたとき。そのような問題のかなり包括的なリストがあります この答え. 。ファクタリング、離散ログ、グラフ変形などの史上最高のお気に入りが含まれています。

興味深いことに、これらの問題のいくつか（注目すべき：ファクタリングと離散ログ）には、量子コンピューターに多項式時間ソリューションがあります（つまり、$ bqp $です）。他のいくつかの問題（グラフ変形など）は$ bqp $であることが知られていないため、質問を解決するための継続的な研究があります。一方、$ npc not subseteq bqp $であると疑われているため、SATの効率的な量子アルゴリズムがあるとは思わない（ただし、二次速度を上げることができる）。心配するのは興味深い質問です $ bqp $になるために必要な構造$ npi $の問題.

Answer 3

いいえ np-Completeの問題があることが知られています p. 。任意の多項式時間アルゴリズムがある場合 np- 問題の問題、次に p = np, 、問題があるからです np それぞれに多項式時間削減があります np-Completeの問題。 （それは実際にどのように」np-complete "が定義されています。）そして明らかに、すべてが np-completeの問題は外にあります p, 、 この意味は p ≠ np. 。何らかの方法でそれを見せることが難しいのか本当に分かりません。その質問に対する答えを知っていれば、おそらくもっと多くを知っているだろう p と np. 。私たちは、私たちが働かないことを知っているいくつかの証拠テクニックを持っています（たとえば、相対化や自然な証拠）が、この問題が難しい理由についての原則的な説明はありません。

に問題がある場合 np 入っていない p, 、それから実際には問題の無限の階層があります np それらの間 p そして、それらのもの np 完了：これは呼ばれる結果です ラドナーの定理.

お役に立てれば！

Answer 4

NPであるいくつかの問題がありますが、それらがnp Completeまたは$ p $であることを誰も知らない グラフ同型¹. 。しかし、私が知っているように、このような問題のための特別な複雑さのクラスはありませんが、私は間違っているかもしれません。

それは$ p $であるかもしれません、例えば前 aks Algorithmプライマリティテストが$ P $またはNPCであることを誰も知っていません。

また、NPCであるが、ではないいくつかの問題があります 強い感覚 また 弱くnp完全, 、 お気に入り 2パーティション 問題は、入力数が入力サイズの多項式順序である場合、この問題は$ p $で解決できます（または、それらには擬似多項式時間アルゴリズムがあります）。

---

¹ 同様の問題： サブグラフ同型 強い意味でNPが完全です。