NP-Completeness
Decision Problems and Optimization Problems
- Optimization problems, each feasible solution has an associated value, and wish to find a feasible solution with the best value. For example, Shortest-Path problem
- Decision problems, answer is simply "Yes" or "No"
- An optimization problem can ben casted to a decision problem by imposing a bound on the value to be optimized. For example, in Shortest-Path problem, find a path from u to v consisting of at most k edges
P
- P is a complexity class that represents the set of all decision problems that can be solved in polynomial time, O(nk)
NP
- NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time
NP-Complete
- NP-Complete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time
- So what makes NP-Complete so interesting is that if any one of the NP-Complete problems was to be solved quickly then all NP problems can be solved quickly
P = NP?
NP-hard
- Intuitively, these are the problems that are at least as hard as the NP-complete problems. Note that NP-hard problems do not have to be in NP, and they do not have to be decision problems
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty |
|---|
| NP-Hard | Yes or No | Unknown | ↑ |
|---|
| NP-Complete | Yes | Unknown | | |
|---|
| NP | Yes | Yes or No | | |
|---|
| P | Yes | Yes | | |
|---|
Reference
