5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ we don't use the NP-hardness of the second problem, we only need to know that it is NP. As @A.Schulz explains you are confused because of thinking about the reduction in the reverse direction (which although exists, is not needed for proving the statement). $\endgroup$ – Kaveh Aug 16 '12 at 21:27
7
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ I underestimated the theorem which proved SAT is NP-complete. Now I realize where my assumptions went wrong. $\endgroup$ – Ankush Aug 17 '12 at 11:30
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I understand your argument. Consider $L_\text{NPC}$ is reduced to $L$ as above. My question is if one solves $L_\text{NPC}$ in polytime, that doesn't solve $L$ in polytime, unless one can reduce $L$ to $L_\text{NPC}$. $\endgroup$ – Ankush Aug 16 '12 at 20:15
  • $\begingroup$ Ankush: You can reduce any NP language to any NP-complete one. That follows from the definition of NP-completeness. $\endgroup$ – sdcvvc Aug 16 '12 at 20:16
  • $\begingroup$ @sdcwc any link? I guess the defn of np-completness is problem is in NP and also in NP-hard. $\endgroup$ – Ankush Aug 16 '12 at 20:22
  • $\begingroup$ Ankush: How do you define NP-hard? $\endgroup$ – sdcvvc Aug 16 '12 at 20:25
  • 1
    $\begingroup$ No, it says that $L$ is at least as hard as $L'$. That's the key here, is that you are showing that a polynomial number of calls to $L$ solves an NP-complete language in polynomial time. Once you prove this, they are equivalent in difficulty. A polynomial-time solution to one implies a polynomial-time solution to the other, and vice versa. $\endgroup$ – jmite Aug 16 '12 at 21:25
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1'd Thanks for giving real number analogy. I underestimated the proof which proved the SAT the 1st NP-complete problem. Basically 1st step in proof that problem is in NP implies it is not more hard than SAT. $\endgroup$ – Ankush Aug 17 '12 at 11:42
  • $\begingroup$ Ankush: Moreover, you don't need SAT, any NP-complete problem suffices by the definition. $\endgroup$ – sdcvvc Aug 18 '12 at 20:44
1
$\begingroup$

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.

$\endgroup$

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.