根据库克定理，
任何 NP 问题都可以在多项式时间内转换为 SAT
我知道SAT是一个NP完全问题。因此，是否准确地说：如果我们可以将搜索问题 A（在 NP 中）以多项式步数简化为问题 B，那么问题 B 一定是 NP 完全的？
问问题
86 次
1 回答
0
您走在正确的轨道上，但还需要做更多工作才能证明问题 A 实际上是 NP 难题。如果你已经证明问题 A 在 NP 中（改写为一个决策问题，描述一个是的证书，并证明它可以在多项式时间内得到验证），那么你必须做的是证明如果你假设找到一个在多项式时间内解决问题 A 的算法，那么该算法也可用于在多项式时间内解决任何 SAT 问题。
这表明您的问题需要您在多项式时间内解决 SAT（以及问题 A 的其他可能输入），并且由于 SAT 尚未在多项式时间内解决，您可以向要求您解决问题的人解释这是一个不合理的要求。为了证明这一点，找到一种方法将 SAT 转换为问题 A 的输入（想想如何将边和顶点转换为问题 A 的输入）。
现在，证明从 SAT 到问题 A 的转换是在多项式时间内完成的，然后证明问题 A 的答案可以转换回 SAT 的答案（同样，在多项式时间内）。最后，请务必说明问题 A 的答案等同于 SAT 的答案（如果问题 A 的答案正确，则 SAT 的答案是正确的）。
对于所有这些步骤，将问题 A 的假设算法视为在多项式时间内神奇地解决问题的黑盒。
于 2019-04-21T19:40:16.520 回答