How are all NP Complete problems similar?

Question

I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps.

1. Prove that current problem is NP, i.e., given a certificate, prove that it can be verified in polynomial time.
2. Take any known NP-complete problem (call "Easy") and reduce all of it's instances to few instances of given problem (call "Hard"). Note this is not necessarily an 1:1 mapping.
3. Prove that above reduction can be done in polynomial time.

All is well here. Is this knowledge right "if you can solve any NP-complete problem in polynomial time, then all NP-complete problems can be solved in polynomial time" ?

If yes, then as per above proof technique, let's say "Easy" problem can be solved in polynomial time, how does that imply "hard" can be solved in polynomial time? What am I missing here? Or is this true, that "hard" problem can be reduced to the "easy" problem too?

Answer 1

Your question seems to come from the fact that you're not immediately convinced that the current problem can't be harder. The current problem can't be harder than any NP-complete problem because it is in NP.

If you want to be convinced that the notion of NP-completeness even exists (i.e. that you can reduce anything in NP to an NP-complete problem) you should study the Cook-Levin theorem which states that SAT is NP-complete.

Since NP-completeness states something about being the target of a reduction from any problem in NP, the proof works by encoding the Turing machine which was the verifier of the original problem as a formula. This formula is satisfiable if and only if there exists an input which lets the Turing machine accept. You could in principle use this proof to reduce your current problem to SAT, and after that to every other NP-complete problem via transitivity of polynomial-time reductions.

(I actually wanted to just add a link to the Cook-Levin theorem in a comment, but this is my first stackexchange post and I think it doesn't let me comment yet.)

Answer 2

You are confused by the direction of the reduction. So let me explain how to argue.

You have a language, say $L$ and you want to show that it is NP-complete. First you show that is indeed in NP, i.e., by finding a good certificate. Thus you are left by showing the NP-hardness. This can be done by reducing some NP-complete language $L_\text{NPC}$ to your language $L$, by a polytime many-one reduction. This means you define a polytime function, that maps yes-instances of $L_\text{NPC}$ to yes-instances of $L$, and that maps no-instances of $L_\text{NPC}$ to no-instances of $L$.

By the transitivity of polytime many-one reductions, every language in NP can now be reduced to $L$ (take a detour over $L_\text{NPC}$). On the other hand, if there exist a deterministic polytime algorithm $A$ that decides $L$, we can decide every language in NP in polynomial time, by first reducing it to $L$ and then asking $A$.

It seems that you have just thought in the wrong direction. The problem that you called "easy", can be solved with help of the reduction and the problem you call "hard". First of all, this is strange misleading terminology, and second, it should probably be the other way around.

Answer 3

Given a set $A \subset \mathbb R$, how do you show that $a$ is a greatest element of the set $A$? There are two steps:

1. Show that $a \in A$.
2. Show that for any $b \in A$, $b \leq a$.

If $a,b$ are greatest elements of set $A$, then applying condition 2 twice (for $a$ and $b$) you get $a \leq b \leq a$. In $\mathbb R$ this means $a=b$ and a set can only have a single greatest element.

---

Now replace $\mathbb R$ by $A^{\ast}$ and $\leq$ by existence of polynomial time reduction. To show that $L$ is NP-complete, there are to steps:

1. Show that $L \in \mathsf{NP}$.
2. Show that for any $L' \in \mathsf{NP}$, $L' \leq L$. This condition is called NP-hardness.

If $L,M$ are two NP-complete languages, then applying condition 2 twice you get $L \leq M \leq L$. Which means the problems are equivalent: if you are able to solve $L$, then you can solve $M$ and vice-versa. Unlike in reals, it might be true that $L \neq M$. Let $L \sim M$ mean $L \leq M \leq L$. You can show this is an equivalence relation.

---

Exercise.

Assume that $M$ is NP-complete, and that $L \sim M$. Show that $L$ is NP-complete.

1. Show that $L \in \mathsf{NP}$.

   Since $M$ is in NP, and $L \leq M$, a machine recognizing $L$ can just use the reduction.

2. Show that for any $L' \in \mathsf{NP}$, $L' \leq L$.

   Since $M$ is NP-hard, $L' \leq M$. Since we know $M \leq L$, by transitivity $L' \leq L$.

---

Therefore, if two languages are NP-complete, they are equivalent. If a language is equivalent to NP-complete language, it is also NP-complete.

Answer 4

There seem to be two misconceptions here.

1. "Easy" and "hard": if anything, it's the other way round. The given problem is "easy" (we don't know its complexity), the other one is known to be hard.
2. "reduce all of it's instances to few instances of given problem": the emphasis is misleading. It's not important how large the reduction's value range is. What is central is that the reduction preserves whether the instance is a YES-instance. In other words, the instance of the NPC problem is a YES instance if and only if its reduction image is a YES instance for the given problem.

Then, what you do is to show that you can solve the hard problem by mapping its instances to instances of the given one (in polynomial time) and solve those. Therefore, the hard problem can not be harder than the given one. Equivalently, the given problem is at least as hard as the hard problem. Quod erat demonstrandum.