爲什麼P⊆co-NP？

Question

我見過幾個地方只是簡單地說明它已知P是NP和co-NP的交集的子集。證明P是NP的一個子集的證明不難找到。因此，爲了表明它是交集的一個子集，剩下要做的就是顯示P是共NP的一個子集。什麼可能證明這是什麼樣的？非常感謝！

Answer 1

類P下互補關閉：如果L是在P一種語言，然後L的補體也是P。您可以通過對L進行多項式時間決策並切換接受狀態和拒絕狀態來看到這一點;這臺新機器現在決定L的補數，並且在多項式時間中這樣做。

A語言L在NP如果它的補碼在NP。因此請考慮任何語言L ∈ P。 L的補體也是P，所以因此L的補體是在NP（因爲P＆subseteq; NP）。因此，L在NP中。因此，P＆subseteq; co-NP。

希望這會有所幫助！

Answer 2

想想這樣。考慮類共同P。由於P在恭維下關閉，P = co-P。

也應該清楚co-P是共NP的一個子集，因爲P包含在NP中。由於P = co-P，因此P包含在共NP中。