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.

  • $\begingroup$ 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? $\endgroup$ – Bader Abu Radi Jan 9 at 22:51
  • $\begingroup$ @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. $\endgroup$ – Ski Mask Jan 9 at 22:53
  • $\begingroup$ The definition of NP-completeness you give is wrong, as it would include all NP-intermediary problems too. $\endgroup$ – 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).


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.