complexity-theory - P = NPの場合、NP-Intermediateは存在できますか？

Question

私の理解では、ラドナーの定理は基本的に次のとおりです。

P！= NPは、NPIがPになく、NPIがNP完全ではない集合NPIが存在することを意味します。

P！=NPではなくP= NPと仮定すると、この定理はどうなりますか？NP中間体が存在しない場合、P=NPであることがわかります。しかし、P = NPの場合、NP中間体は存在できますか？

Answer 1

NPIは、それがNPにあることを意味する必要がありますが、NP完全ではないことを意味します。

P = NPの場合、PとNPのすべての問題はNP完全になります。これは、任意の問題を多項式時間で別の問題に還元できるためです（∅とΣ*は、任意の問題をマッピングできないため、NP完全にすることはできません）。どちらにも-ポジティブ/ネガティブの場合にマップするものはありません。ただし、これらはPであるため、この質問の目的では気にしません。）

NPのすべての問題はNP完全であるため、NPIは存在できません。

Answer 2

NPIの1つのプロパティを見逃しました：NPIのすべての要素はNPにあります（ただし、Pにはありません）。P = NPの場合、これは明らかに不可能です。したがって、P = NPの場合、NPIは空である必要があります。

Answer 3

P = NPの場合、すべてのNPがPに含まれ、したがってNPIの定義の「notin P」の部分は問題を起こさないため、NPIはNPのサブセットであると想定して存在できません。したがって、その場合、クラスNPIは空になります。

Answer 4

古典的な定式化におけるラドナーの定理は、P=NPの場合について何も述べていません。

基本的なロジックから、$ A \ rightarrow B$は$not（A）$について何も述べていません...残念ながら。

さらに、$ P = NP $で、$NP$が$NP-complete$にクック削減可能である場合、計算（加算、フーリエ変換、並べ替え）で計算するほとんどの問題は、次のように削減可能であることを意味します。 、サブセット和....クックの定理が有効であると仮定します。これはかなり気が遠くなるでしょう。

しかし、ラドナーの定理から、$ P =NP$の場合については何でも言うことができます。