complexity-theory - 为什么SAT的补语不在NP中？

Question

我知道你们不能给验证证书。但是，我只是在想，为什么我们不能将输入输入到决定 SAT 的 NDTM，然后反转答案呢？漏洞在哪里？

Answer 1

其实不知道SAT的补语是不是NP。如果 P = NP，那么由于所有 P 语言在补码下都是封闭的，因此 SAT 的补码必须在 NP 中(因为它在 P 中)。否则，如果SAT的补集不在NP中，则同理P≠NP。

怀疑 SAT 的补码不在 NP 中，因为 SAT 的补码由(忽略垃圾格式错误的字符串)不可满足的命题公式组成。目前尚不清楚您可以不确定地猜测哪些信息可以帮助您确定公式是否永远不会计算为真，而在 SAT 的情况下，很容易不确定地猜测令人满意的作业以检查公式是否确实可满足。

至于您推理中的错误 - NTM 接受当且仅当存在一些 接受计算分支。如果将所有“接受”翻转为“拒绝”，则不会翻转计算的整体结果。要翻转计算结果，您必须让补充的 NTM 接受当且仅当 每个 分支都接受，而不是如果至少一个 分支接受。

希望这对您有所帮助!