|
P, NP, CO-NP, NP-complete, NP-hard
|
| Problem |
Description |
Best Approximate Time Complexity |
|
| NP |
NP is the set of decision problems solvable in polynomial time on a nondeterministic Turing machine. Or, equivalently,
YES answers are checkable in polynomial time on a deterministic Turing machine |
|
| CO-NP |
For every decision problem in NP, Co-NP contains the same decision
problem with the YES and NO answers swapped. |
|
|
|
|
| NP-complete |
The complexity class NP-complete is the set of problems that are the hardest problems in NP, in the sense that they
are the ones most likely not to be in P. If you can find a way to solve an NP-complete problem quickly, then you can use that algorithm to
solve all NP problems quickly. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| NP-hard |
A set or property of computational search problems (generally: all construction problems of
corresponding NP-complete decision problems are NP-hard)
A problem is NP-hard if solving it in polynomial time would make it possible to solve all problems
in class NP in polynomial time. Some NP-hard problems are also in NP (these are called "NP-complete"),
some are not. If you could reduce an NP problem to an NP-hard problem and then solve it in
polynomial time, you could solve all NP problems. Also, there are decision
problems in NP-hard but are not NP-complete, such as the infamous halting
problem |
|
| Knapsack problem |
|
|
|
|