What is the definition of P, NP, NP-complete and NP-hard?

here is a good answer but it really doesn't answer mym question.

np-hard-: a problem A is NP hard if for all B$\in$NP, B is polynomial time reducible to A.(i.e A is easier than B). Then why is A called NP Hard? It should be called NP easy problem? Isn't it?

np complete-: A problem is NP complete if problem is in both NP and NP hard.

SO basically np complete=np hard. What is the difference between np hard and np complete?


1 Answer 1


So I got it. NP hard problem is not necessarily in NP. That's the difference.


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.