2
$\begingroup$

As we all know the million dollar question in Computer Science P=NP or not. I was trying to understand it and got some doubts please tell me whether I'm right or wrong

N=NP in two cases

Case 1: We have found an algorithm which can solve a NP-Complete problem in P-Time. This implies that P=NP=NP-Complete. But still we can not say anything about the NP-HARD Problems.

http://s30.postimg.org/k721ni0j5/image.png

Case 2: We have found an algorithm which can solve a NP-Hard problem in P-Time. This implies that P=NP=NP-Complete=NP-Hard.

http://s15.postimg.org/3po7i4kcr/image.png

Am I right or I'm missing some point.

|cite|improve this question
$\endgroup$
  • $\begingroup$ You can include the images in the post, rather than just as links. $\endgroup$ – Dave Clarke Feb 15 '14 at 12:10
6
$\begingroup$

Case 1 is almost correct: if you could solve a single NP-complete problem in polynomial time, then every other NP problem can be solved by first reducing to the solved problem and then using the polytime algorithm for that. However, even if P NP, the trivial languages $\emptyset$ and $\Sigma^*$ are not NP-complete under many-one reductions, so NP $\neq$ NP-complete.

Case 2 is incorrect. NP-hard is not a complexity class, as such, and NP-hard problems can have arbitrarily high complexity. To take an extreme case, the halting problem in NP-hard but you wouldn't be able to solve that by proving P = NP. Also, any EXP-complete problem is NP-hard, since NP $\subseteq$ EXP, so any problem in NP is reducible to any EXP-complete problem. However, by the time hierarchy theorem, P $\neq$ EXP so there cannot, in fact, be any polytime solution to this NP-hard problem, even if P = NP.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

No, your case 2 is wrong.

NP-hard is definitely not equal to P. NP-hard includes problems that are not even decidable/computable.

The following diagram might help: it shows that there is no upper bound on how hard NP-hard problems can be.

NP-hard problems are not bounded above

If we solve some problem in polynomial time, then all problems below that in the diagram will be solvable in polynomial time but there are still NP-hard problems above it which are not.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Is this Definition is right "A problem ‘h’ is NP-hard if and only if there is an NP-complete problem ‘c’ that is P-Time reducible to ‘h’ (Cook Reduction). But since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in P-Time. Then if there is a solution to one NP-hard problem in P-Time, there is a solution to all NP-Complete problems in P-Time." $\endgroup$ – Atinesh Feb 15 '14 at 11:23
  • 1
    $\begingroup$ That is correct (though it's not a definition). A solution in polynomial time to one NP-hard problem gives a polynomial time algorithm for all NP-complete problems (actually all NP problems), but not to all NP-hard problems. $\endgroup$ – Max Feb 15 '14 at 11:26
  • $\begingroup$ Can u explain Diagrammatically the meaning of "Then if there is a solution to one NP-hard problem in P-Time, there is a solution to all NP-Complete problems in P-Time." $\endgroup$ – Atinesh Feb 15 '14 at 12:02
  • $\begingroup$ Is this the correct diagrammatic representation for Case 2 s29.postimg.org/d1u517orr/qwq.png $\endgroup$ – Atinesh Feb 15 '14 at 16:03
  • $\begingroup$ you mean for both the 2 above cases the single diagram that you have showed is correct. $\endgroup$ – Atinesh Feb 16 '14 at 8:46

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.