事实上,SAT的补集是否属于NP仍未知。如果P = NP,则由于所有P语言都在补集下封闭,因此SAT的补集必须属于NP(因为它在P中)。否则,如果SAT的补集不属于NP,则可以使用类似的逻辑证明P ≠ NP。据推测,SAT的补集不属于NP,因为SAT的补集(忽略垃圾格式错误的字符串)由无法满足的命题公式组成。目前还不清楚您可以随意猜测哪些信息来帮助您确定一个公式永远不会评估为true,而在SAT的情况下,可以随意猜测一个满足的分配来检查一个公式是否确实可满足。至于您推理中的错误 - 如果NTM接受,则计算中有某些接受分支。如果将所有“接受”翻转为“拒绝”,则不会翻转计算的总体结果。要翻转计算结果,您需要使补充的NTM接受当且仅当每个分支都被接受,而不是当至少有一个分支被接受时。希望这能帮到您!