爲什麼星期六不補充NP？

我知道您無法提供驗證證書。但是，我只是在想，爲什麼我們不能給NDTM決定SAT的輸入，然後改變答案呢？缺陷在哪裏？爲什麼星期六不補充NP？

2013-10-21 Prashant

實際上不知道SAT的補充是否在NP中。如果P = NP，那麼由於所有P語言都在互補下關閉，所以SAT的補碼必須在NP中（因爲它在P中）。否則，如果SAT的補碼不在NP中，則使用類似的邏輯。

這是疑似由於補充SAT包含（忽略垃圾格式不正確的字符串）的命題公式是不可滿足的，所以SAT的補碼不在NP中。目前還不清楚哪些信息可以非確定性地猜測，這將有助於確定公式是否從未評估爲真，而在SAT的情況下，很容易以非確定的方式猜測滿意的分配以檢查公式是否確實可滿足。

至於你的推理錯誤 - 一個NTM接受iff有一些接受計算的分支。如果您將所有「接受」都翻轉爲「拒絕」，那麼您不會翻轉計算的總體結果。爲了翻轉計算結果，如果至少有一個分支接受，則必須讓補充的NTM接受ifff 分支接受的每個，而對於。

希望這會有所幫助！

2013-10-21 01:34:32 templatetypedef

謝謝，但我仍然困惑，假設我有一個NDTM A決定SAT。我有一個x，我想決定它是否屬於SAT補碼。我在A上運行輸入，如果它接受（即接受任何分支），我拒絕其他拒絕（即所有分支拒絕）的我接受。 – Prashant

@ user96758-如果您可以運行NDTM完成並查看結果，則確實可以將其翻轉。但是，您無法構建NDTM以機械方式執行該過程。試着考慮NDTM如何工作，我想你會看到一個問題出現。 – templatetypedef

是的，也許我不能建立它，但是這整個過程不會補充SAT在NP中，因爲我可以在非確定性多項式時間通過在SAT NDTM上運行輸入來確定它。 – Prashant

回答