# 2 cases for P = NP

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. 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. Am I right or I'm missing some point.

• You can include the images in the post, rather than just as links. – Dave Clarke Feb 15 '14 at 12:10

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.

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

• 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." – Atinesh Feb 15 '14 at 11:23
• 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. – Max Feb 15 '14 at 11:26
• 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." – Atinesh Feb 15 '14 at 12:02
• Is this the correct diagrammatic representation for Case 2 s29.postimg.org/d1u517orr/qwq.png – Atinesh Feb 15 '14 at 16:03
• you mean for both the 2 above cases the single diagram that you have showed is correct. – Atinesh Feb 16 '14 at 8:46