我知道您不能提供验证证书。但是，我只是在想，为什么我们不能将输入提供给决定 SAT 的 NDTM，然后反转答案？缺陷在哪里？
问问题
3044 次
1 回答
5
实际上不知道SAT的补码是否在NP中。如果 P = NP，那么由于所有 P 语言在补码下都是封闭的，那么 SAT 的补码必须在 NP 中（因为它在 P 中）。否则，如果SAT的补码不在NP中，则使用类似的逻辑，P≠NP。
怀疑SAT的补码不在 NP 中，因为 SAT 的补码由不可满足的命题公式组成（忽略垃圾格式错误的字符串）。目前尚不清楚您可以不确定地猜测哪些信息将帮助您确定公式是否永远不会评估为真，而在 SAT 的情况下，很容易不确定地猜测一个令人满意的分配以检查公式是否确实可满足。
至于您推理中的错误 - NTM 接受如果有一些计算的接受分支。如果您将所有“接受”翻转为“拒绝”，那么您不会翻转计算的整体结果。要翻转计算结果，如果每个分支都接受，则必须让补充的 NTM 接受，而不是至少一个分支接受。
希望这可以帮助！
于 2013-10-21T01:34:32.767 回答