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