# Symmetry of NP completeness

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?

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

[...] 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.

• 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? – ZeroKnowledge Apr 17 at 21:45

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.

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