NPとCO-NPの1つはPに等しいことができますか？

Question

たぶん私は明らかな何かを見逃しているかもしれませんが、それはp = co-np $ subsetneq $ npまたはその逆である可能性がありますか？私の気持ちは、この可能性を排除する定理があるに違いないということです。

Answer 1

いいえ、$ mathsf {p} $がこれを補完するために閉じているため、$ mathsf {p} = mathsf {np} は mathsf {np} = mathsf {co text { - } np} $。

$ mathsf {p} = mathsf {np} $、および$ l in mathsf {co text { - } np} $を削除すると仮定しましょう。 。 $ mathsf {p} = mathsf {np} $を想定したため、tm $ m $ $ $ $ l（m）= l^c $が存在します。 $ m $の「補完」を取ると、それは$ m $と同じマシン$ m '$であり、その受け入れと拒否の状態が逆になっていることを除いて、$ l（m'）=（l^cを取得します）^c = l $、したがって$ l $は$ mathsf {np} $です。

これは、$ mathsf {p} = mathsf {np} $という仮定の下で、$（ mathsf {p} =） mathsf {np} = mathsf {co text { - } np}を取得することを示しています。 $、したがって$ mathsf {p} = mathsf {co text { - } np} $。

Answer 2

$ mathsf {p} $は補完の下で閉じられています（ie $ mathsf {p} = mathsf {co text { - } p} $¹）;したがって、$ mathsf {p} = mathsf {co text { - } np} $（または$ mathsf {p} = mathsf {np} $）then $ mathsf {co text { - } np} = mathsf {np} $

---

1. 言語$ l in mathsf {p} $を考えると、$ l $ and ...を決定するtmを取得するだけで、多項式時間で$ overline l $を決定する決定論的tm 'を構築できます。