Computational Complexity リファレンス
リファレンス 用 complexity クラス: P, NP, PSPACE, および hardness reductions.
Complexity Classes
P is the class of problems solvable in polynomial time. NP is solvable in polynomial time by a nondeterministic machine (verifiable in poly time). coNP is the complement of NP. PSPACE is solvable in polynomial space. EXPTIME requires exponential time. The P vs NP question (open) asks if every verifiable problem is solvable. NP-complete problems are the hardest in NP; solving one in poly time solves all. NP-hard problems are at least as hard as NP but may not be in NP. Reductions show relative hardness: A reduces to B means B is at least as hard as A.
- P
- Poly time solvable
- NP
- Poly time verifiable
- NP-complete
- Hardest in NP
efficientnondeterministicSAT, TSPNotable Problems and Reductions
SAT (Boolean satisfiability) is the first NP-complete problem (Cook-Levin). 3-SAT, clique, vertex cover, Hamiltonian path, TSP (decision), and knapsack are NP-complete. Factoring and discrete log are in NP ∩ coNP, believed not NP-complete. Graph isomorphism is in a special class (quasi-polynomial algorithm exists). #P counts solutions to NP problems (#SAT). BPP is probabilistic polynomial time; most believe BPP = P (derandomization). Quantum complexity: BQP contains factoring (Shor) but relationship to NP is open. The polynomial hierarchy generalizes NP and coNP. Space complexity: L ⊆ NL ⊆ P, Savitch's theorem NL = coNL.
- SAT
- First NP-complete
- factoring
- NP ∩ coNP
- BQP
- Quantum poly time
Cook-Levinnot NP-complete?Shor in BQP