爲什麼co-P = P

Question

更具體地說，爲什麼有一個TM接受和停止P中的任何補語？ 據我所知，有一個TM拒絕了來自P的語言L，但爲什麼必須有一個TM接受L的補碼？

Answer 1

簡單的解決方案：設L是圖靈機M接受語言L的原始語言。要計算L補充，創建一個新機器M'，使得M'與M相同，除了我們切換所有轉換到M的接受狀態爲「拒絕狀態」，並且全部轉換到拒絕狀態（或「格式錯誤的轉換」）到接受狀態。

M'的運行時間與M的運行時間相同。當M拒絕/接受時，它將完全接受/拒絕。

---

一位評論者問我是否可以提供直覺爲什麼這不適用於NP與co-NP。它在這裏有助於從庫克萊文對語言L在NP中的定義開始，它允許明確定義語言L'在NP-NP中的定義。 （使用基於非確定性圖靈機的定義使得共NP的定義更難）

在Cook-Levin定義中，語言L在NP中，如果我們有一個「驗證」圖靈機V這樣對於L中的所有字符串S，都有一個多項式長度的有界證書字符串C，使得V接受這對（S，C）（把V想象成雙帶輸入機器，否則認爲它接受該對輸入的編碼）。另外當然，我們要求V在多項式時間內完成驗證。

作爲一個例子，對於3SAT語言，字符串S將是3SAT問題實例語句，並且證書C將是變量的真值分配。驗證者V將查看真值分配並檢查3SAT問題實例的每個子句是否都使用該真值分配進行驗證。

所以把簡潔爲NP語言L是通過其核查圖靈機五所述，我們說：

所以來形容補語言，L」我們有：

如果我們想「嘗試同樣的伎倆」爲NP VS反NP，因爲我們沒有對於P VS共同-P，機會並沒有真正提出自己好。我們或者需要嘗試一個確定性的圖靈機，它可以完全解決每個實例的語言（並且可能沒有多項式時間運行邊界），或者我們需要看看我們是否可以通過將這個技巧應用於V如果我們簡單地交換驗證機器V的結果，我們仍然需要檢查每可能的證書C以查看給定的字符串S是否真的不被V接受。