P: A decision problem that
can be solved in polynomial time. That is, given an instance of the problem, the
answer yes or no can be decided in polynomial time.
NP: A decision problem where instances of the
problem for which the answer is yes have proofs that can be verified in
polynomial time (We know the answer, and verified the answer takes
polynomial time). This means that if someone gives us an instance of the problem
and a certificate (sometimes called a witness) to the answer being yes, we can
check that it is correct in polynomial time.
NP-complete: An NP problem X for which it is
possible to reduce any other NP problem Y to X in polynomial
time (Any NP Problem can reduce to
NP-Complete in polynonial time). Intuitively this means that we can solve Y quickly if we
know how to solve X quickly.
What makes
NP-complete problems important is that if a deterministic polynomial time
algorithm can be found to solve one of them, every NP problem is solvable in
polynomial time (one problem to rule them all).
NP-hard: Intuitively these are the problems that
are even harder than the NP-complete problems. Note that NP-hard
problems do not have to be in NP (they do not have to be
decision problems). The precise definition here is that a
problem X is NP-hard if there is
an NP-complete problem Y such
that Y is reducible to X in polynomial time (Any NP-Complete problem
can reduce to NP-Hard in polynonial time).
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 polynomial time. Then if there is a solution to one NP-hard problem in
polynomial time, there is a solution to all NP problems in polynomial time.
from <http://stackoverflow.com/questions/1857244/np-vs-np-complete-vs-np-hard-what-does-it-all-mean>
• P:
The complexity class of decision problems that can be
solved on a deterministic Turing machine in polynomial time.
• NP: The
complexity class of decision problems that can be solved on
a non-deterministic Turing machine in polynomial time.
No comments:
Post a Comment