Based on Cook's theorem,

Any NP problem can be converted to SAT in polynomial time

I know that SAT is a NP-complete problem. Therefore, is it accurate to say: If we can reduce a search problem A (which is in NP) to problem B in a polynomial number of steps, then problem B must be NP-complete?


You are on the right track, but there is a little bit more that must be done to show that problem A is in fact NP hard. If you have already proven that problem A is in NP (reword as a decision problem, describe a yes certificate, and show that it can be verified in polynomial time), then what you must do is show that if you were to hypothetically find an algorithm that solves problem A in polynomial time, then that algorithm could be used to solve any SAT problem in polynomial time as well.

This shows that your problem requires you to solve SAT (as well as other possible inputs for problem A) in polynomial time, and since SAT has yet to be solved in polynomial time, you can explain to whoever is asking you to solve the problem that this is an unreasonable request. To show this, find a way to convert SAT into input for your problem A (think how to transform the edges and vertices into the input of problem A).

Now, show that this transformation from SAT to problem A is done in polynomial time, and then show that the answer from problem A can be transformed back into an answer for SAT (again, in polynomial time). Lastly, make sure to explain that an answer to problem A is equivalent to an answer to SAT (the answer to SAT is correct IFF the answer to problem A is correct).

For all of these steps, treat the hypothetical algorithm for problem A as a black box that magically solves the problem in polynomial time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.