0

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

Edited by pritaeas: Moved to Computer Science.

3
Contributors
4
Replies
18
Views
2 Years
Discussion Span
Last Post by Schol-R-LEA
0

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.

0

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.

Edited by Schol-R-LEA

0

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.