NP vs NP-Complete vs NP-Hard — what does it all mean?

[Baalla]

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

[sepp2k]

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.

[Schol-R-LEA]

For the sake of clarification:

• NTM - Non-Deterministic Turing Machine
• DTM - Deterministic Turing Machine
• NP - Non-deterministic Polynomial complexity, used to describe the computational complexity of a problem or (less formally) an algorithm to solve said problem - usually describing its time complexity, though in principle it could be used to describe space complexity as well. An NP problem can, in principle, be solved using a Non-Deterministic Turing Machine in polynomial time - while the Church-Turing Thesis asserts (though to date does not prove) that all decidable problems can be computed on any Turing-complete computation system, all NP (or NP-hard) problems are believed to have no solutions using a deterministic Turing machine that would not exceed polynomial time, but would have a solution in polynomial time on a non-deterministic Turing machine.
• P - (deterministic) Polynomial complexity - a narrower and more tractable sub-set of the NP problems which can be solved using a Deterministic Turing Machine in polynomial time. The question of whether P = NP (that is, whether all NP problems have deterministic solutions in polynomial time) is an open research problem, one which many suspect (but so far have not proven) is undecidable.

[sepp2k]

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.

[Schol-R-LEA]

Ah, thank you for that correction.