2
$\begingroup$

To show that some problem X is NP-complete, we usually show that it is in NP and that an efficient algorithm for deciding X implies an efficient algorithm for deciding some known NP-complete problem like SAT.

At the same time, informally, the NP-completeness definition usually says that solving any single NP-complete problem implies a solution to all NP-complete problems.

If both statements above are correct, then the above "proof approach" (showing that "solving X" $\implies$ "solving SAT") also somehow implies that an efficient algorithm for SAT implies an efficient algorithm for X. In general reductions are not symmetric, so why is this the case here?

$\endgroup$
  • 1
    $\begingroup$ It doesn’t. The other direction follows from the Cook-Levin theorem, and only requires X to be in NP. $\endgroup$ – Yuval Filmus Apr 16 at 4:19
  • $\begingroup$ thanks! I'll have a look at it. $\endgroup$ – ZeroKnowledge Apr 17 at 21:42
3
$\begingroup$

[...] an efficient algorithm for deciding X implies an efficient algorithm for deciding some known NP-complete problem like SAT.

Be careful with this! In the context of NP-completeness we work with many-one reductions, not Turing reductions. This means you are not allowed to assume the existence of an efficient algorithm for $X$; this is too strong an assumption since it would allow you arbitrary access to the algorithm deciding $X$. Rather, you must reduce SAT to an instance of $X$. In fact, it is irrelevant whether $X$ can be solved efficiently or not (or even solved at all!). This establishes NP-hardness; for NP-completeness you also need to show $X \in \textbf{NP}$.

Note it is only once you have established NP-hardness of $X$ that you can say the existence of an efficient algorithm for $X$ implies the existence of an efficient algorithm for SAT (or any problem in NP). However, this is only an implication of the NP-hardness of $X$, not the actual requirement for $X$ being NP-hard.

$\endgroup$
  • $\begingroup$ I'm not sure I fully understand the distinction you make. I don't assume an efficient algorithm for solving X. As far as I understand, I just show that if solving X is easy, then solving SAT is equally easy (up to polynomial factors). Can you clarify what exactly you mean? The point you make is that a reduction would not be allowed to make non-blackbox access to an assumed algorithm? $\endgroup$ – ZeroKnowledge Apr 17 at 21:45
1
$\begingroup$

At the same time, informally, the NP-completeness definition usually says that solving any single NP-complete problem implies a solution to all NP-complete problems.

Correct, only it implies a solution to any NP problem, yours is a weaker statement. To be precise, a polynomial time solution to an NP-complete problem implies a polynomial time solution to any NP problem.

If both statements above are correct, then the above "proof approach" (showing that "solving X" ⟹ "solving SAT") also somehow implies that an efficient algorithm for SAT implies an efficient algorithm for X.

Yes, only the fact that "solving SAT"⟹ "solving X" is already true as per your first statement (a consequence of the Cook-Levin Theorem), and the result stands independent of this reduction. You might want to take a look at Karp and Cook reductions, as others have pointed out, as NP-completeness is usually defined in terms of Karp reductions, so "solving A" ⟹ "solving B" where B is NP-complete does not necessarily mean A is NP-complete in the sense of Karp reductions.

$\endgroup$
  • $\begingroup$ thanks for the pointers. I'll have a look at the Cook-Levin Theorem and the reduction types that you mentioned. $\endgroup$ – ZeroKnowledge Apr 17 at 21:40

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.