为什么SAT的补集不属于NP？

Question

我知道你不能给出一个验证证书。但是，我在想，为什么我们不能将输入提供给决定SAT的NDTM，然后反转答案呢？这里有什么漏洞吗？

- Prashant

Answer 1

事实上，SAT的补集是否属于NP仍未知。如果P = NP，则由于所有P语言都在补集下封闭，因此SAT的补集必须属于NP（因为它在P中）。否则，如果SAT的补集不属于NP，则可以使用类似的逻辑证明P ≠ NP。

据推测，SAT的补集不属于NP，因为SAT的补集（忽略垃圾格式错误的字符串）由无法满足的命题公式组成。目前还不清楚您可以随意猜测哪些信息来帮助您确定一个公式永远不会评估为true，而在SAT的情况下，可以随意猜测一个满足的分配来检查一个公式是否确实可满足。

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

希望这能帮到您！

- templatetypedef

---

谢谢，但我仍然困惑，假设我有一个决定SAT的NDTM A。我有一个x，我想确定它是否属于SAT补集。我在A上运行输入，如果它被接受（即任何分支被接受），我拒绝；否则，如果它被拒绝（即所有分支都被拒绝），我接受。 - Prashant

@user96758- 如果您能够运行 NDTM 并查看结果，确实可以翻转它。但是，您无法构建一个 NDTM 来机械化执行该过程。尝试思考一下这个 NDTM 如何工作，我认为您会发现一个问题出现了。 - templatetypedef

是的，也许我无法构建它，但整个过程难道不会使补集SAT成为NP问题吗？因为我可以通过在SAT NDTM上运行输入来在非确定性多项式时间内决定它。 - Prashant

@user96758- 为了使SAT的补集属于NP，需要存在一个多项式时间的非确定性图灵机来决定SAT的补集。仅凭借一个带有NDTM的人类操作员可以确定一个字符串是否在SAT的补集中是不够的；必须要有一个单独的NDTM，在没有用户帮助的情况下决定SAT的补集。这样说您是否明白？ - templatetypedef

是的，我明白了。谢谢！ - Prashant