NP中間の問題とは何ですか？

Question

仮定P！= NP

オイラー図は、PおよびNP完全な部分ではない部分を示しています。私はこのセットがNP-中級と呼ばれるウィキペディアで読む。

Euler Diagram

私は、NPIの問題が定義されている方法についてのいくつかの疑問がありますか？

Answer 1

NP - 中間体の問題は

• がにNP（つまり、 "はい" の回答が多項式時間で検証することが可能である）、
• がではないからである意思決定の問題ですP（つまり、問題解決のための多項式時間アルゴリズムはありません）、
• はNP -completeではありません。

最後の基準は、さまざまな方法で記述できます。これを言う1つの方法は、SATからその特定の問題への多項式時間マッピングの削減がないことです。

我々はどのNP - 中間の​​問題が存在するかどうかわからないので、これらの問題は今、主に理論的な関心のある - 私たちはものを見つけることができれば、我々はPではありませんNPで問題を抱えていると思います、つまり、P ≠ NP！私たちはそのP ≠ NPを証明できる場合しかし、彼らは面白いですし、我々は多項式時間で解くことには余りにも難しいですでいくつかの問題NPがあることを知っているが、その中ではありませんNP（問題はNP -complete）のハード問題の「最も難しい」。イベントで

あなたはPにNPに問題を持っていますがないことができなかったので、P = NPは、その後、任意のNP - 中間の​​問題がないだろうと。 NPP ≠ 場合、ラドナーの定理を保証少なくとも1 NP - 中間の​​問題が存在するが、特に非常に人工的であるという問題を構築することにより、そうしその場合のNP - 中間体であることを専ら設計されています。今のところ、いくつかの例外（特にgraph isomorphism problem）で、我々はにおけるNPの知っているすべての問題は、PまたはNP -completeあることが知られている中で真正面いずれかです。