# Clarifying the definition of reduction with regards to NP-complete problems

In my logic class we started learning about the different complexity classes. In particular, we focused on the NP complexity class. A problem is in NP if it is solvable in polynomial time using a nondeterministic Turing machine. To show that a problem $$L$$ is NP-compelete, we have to show that: $$1)$$ $$L$$ is in NP, and $$2)$$ if $$L$$ is solvable in polynomial time, then all problems in NP can be solved in polynomial time.

In regards to $$2)$$ we can use reduction. So if you already know a NP-complete problem $$M$$, then it is enough to show that we can use a polynomial time algorithm that we can use for $$L$$, in order to solve $$M$$ in polynomial time.

I'm not sure I understand the explanation for the reduction section.

• So in simple terms your question is: if $L$ is NP-complete and $L\in P$, then why we can solve all problems in NP in polynomial time? Jan 9 at 22:51
• @BaderAbuRadi In my script it says that "2) L is NP". And yes. That is what I would like to know along with a clear explanation of what the explanation of reduction is trying to say. Jan 9 at 22:53
• The definition of NP-completeness you give is wrong, as it would include all NP-intermediary problems too.
– Arno
Feb 9 at 9:18

A problem $$L$$ is $$\text{NP}$$-complete if $$L$$ is in $$\text{NP}$$, and $$L$$ is $$\text{NP}$$-hard (that is, $$A\leq_p L$$ for all $$A\in \text{NP}$$ ). Consider the following claims.
Claim 1: if $$L$$ is $$\text{NP}$$-complete and $$L\in \text{P}$$, then $$\text{NP} \subseteq \text{P}$$ (that is, all problems in $$\text{NP}$$ can be solved in deterministic polynomial time).
Claim 2: If $$A \leq_p B$$, then $$B\in \text{P} \to A \in \text{P}$$.
What you asked about is claim 1. To begin with, its correctness follows from claim 2. Indeed, if $$L$$ is $$\text{NP}$$-complete, then for every $$A\in \text{NP}$$, it holds that $$A\leq_p L$$. Thus, if we assume that $$L\in \text{P}$$, then we get by claim 2 that $$A\in \text{P}$$, and therefore $$\text{NP} \subseteq \text{P}$$. So what is missing for you is the proof of claim 2, and a sketch of its proof goes as follows. If $$M_f$$ is a TM that computes a polynomial time reduction $$f$$ from $$A$$ to $$B$$, and $$M_B$$ is a TM that decides $$B$$ in polynomial time, then a TM $$M_A$$ that decides $$A$$ in polynomial time operates as follows. On input $$x$$, $$M_A$$ computes $$y = M_f(x)$$, then $$M_A$$ runs $$M_B$$ on $$y$$, and answers the same. What is left to show is that $$M_A$$ decides $$A$$ in polynomial time, and I leave that to you (use the fact that |y| is polynomial, and the fact that a composition of polynomials is a polynomial).