What are the differences between NP vs NP-Complete vs NP-Hard ?
I am aware of many resources all over the web. I'd like to read your explanations to undrestand better
What are the differences between NP vs NP-Complete vs NP-Hard ?
I am aware of many resources all over the web. I'd like to read your explanations to undrestand better
Jump to PostNP means a NTM can solve it in polynomial time (or equivelantly that a DTM can verify the result in polynomial time). Note that NP is a superset (possibly, but not necessarily, a proper superset) of P, meaning that everything in P is also in NP.
A problem X being …
NP means a NTM can solve it in polynomial time (or equivelantly that a DTM can verify the result in polynomial time). Note that NP is a superset (possibly, but not necessarily, a proper superset) of P, meaning that everything in P is also in NP.
A problem X being NP-hard means that every problem in NP is reducible in polynomial time to X. Intuitively this means that X is at least as hard as every problem in NP. Note that this does not mean that X itself must be in NP.
A problem is NP-complete if it is both NP-hard and in NP.
For the sake of clarification:
usually describing its time complexity, though in principle it could be used to describe space complexity as well.
No, you're probably thinking of Big-Oh (which is most often used to describe time, but can also be used to describe space - or anything else). P is specifically the set of problems that, for some constant c
, can be solved in O(n^c)
time on a DTM (same for NP and NTMs). If you want the same thing for space, there's the PSPACE class, which is a very different class. P and PSPACE can not be used interchangeably.
Ah, thank you for that correction.
We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.