NP-completeness

Definition

In computational complexity theory, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. Somewhat more precisely, a problem is NP-complete when:It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". Each input to the problem is associated with a collection of short solutions, which might or might not validly solve the input. The output is "yes" when at least one of these solutions is valid, and "no" when none of them are. The validity of each solution can be verified quickly, and a brute-force search algorithm can find a valid solution by trying all possible solutions. The problem can be used to simulate every other problem for which we can verify quickly that a solution is valid. Hence, if we could find valid solutions of some NP-complete problem quickly, we could quickly find valid solutions for every other problem in which a given solution can be easily verified.

Related concepts

2-EXPTIME 2-satisfiability 3-satisfiability AC0 ACC0 ALL (complexity)APX Abstract machine Alfred Aho Algorithm Almost complete Approximation algorithm Arithmetical hierarchy Arthur–Merlin protocol BPP (complexity)BQP Bipartite graph Boolean hierarchy Boolean satisfiability problem Brute-force search CC (complexity)Charles E. Leiserson Christos Papadimitriou Clay Mathematics Institute Clifford Stein Clique problem Co-NP Co-NP-complete Commun. ACM Complement (complexity)Complete (complexity)Complexity class Computational complexity theory Computer programmer Computer scientist Computers and Intractability Concatenation Cook–Levin theorem Cycle graph DLOGTIME DSPACE DTIME David S. Johnson Decision problem Deterministic Deterministic algorithm Dominating set problem Dominic Welsh Don Knuth Donald Knuth ELEMENTARY EXPSPACE EXPTIME Euler diagram Exponential hierarchy FL (complexity)FNP (complexity)FP (complexity)Gadget (computer science)Galley proofs Gerhard J. Woeginger Graph coloring problem Graph isomorphism Graph isomorphism problem Graph theory Grzegorczyk hierarchy Halting problem Hamiltonian path problem Hans L. Bodlaender Heuristic (computer science)IP (complexity)Independent set problem Information-theoretic security Interactive proof system Intersection Introduction to Algorithms Isomorphic Isomorphism Jeffrey Ullman John Hopcroft Karp's 21 NP-complete problems Kenneth Steiglitz Kleene star Knapsack problem L (complexity)Labours of Hercules Ladner's theorem Lance Fortnow List of NP-complete problems List of complexity classes List of open problems in computer science Logarithmic-space many-one reduction Logarithmic space Manindra Agrawal Many-one reduction Marek Karpinski Metaheuristic Michael Garey Michael Sipser Millennium Prize Problems Minimum spanning tree NC (complexity)NEXPTIME NL-complete NL (complexity)NONELEMENTARY NP-Intermediate NP-hard NP-hardness NP (complexity)NSPACE NTIME National Central University National Tsing Hua University Nondeterministic Turing machine Open problem P-complete PP (complexity)PR (complexity)PSPACE PSPACE-complete P (complexity)P = NP problem P versus NP problem Parameterized complexity Parity P Planar graph Planar separator theorem PolyL Polynomial-time reduction Polynomial hierarchy Polynomial time Presburger arithmetic Probabilistically checkable proof QMA Quasi-polynomial time RE (complexity)RL (complexity)RP (complexity)R (complexity)Reduction (complexity)Regular language Richard J. Lipton Richard Karp Robert Tarjan Ronald L. Rivest SC (complexity)SIAM Journal on Computing SIGACT SL (complexity)Scott Aaronson Stanford University Stephen A. Cook Steven Rudich Strongly NP-complete Subgraph isomorphism problem Subset sum problem Sudoku Superpolynomial Symposium on Theory of Computing TC0 TC (complexity)TFNP Theoretical computer science Thomas H. Cormen Toniann Pitassi Travelling Salesman (2012 film)Travelling salesman problem Turing completeness Turing machine Turing reduction UP (complexity)Union (set theory)Universal Turing machine University of Liverpool Valiant–Vazirani theorem Vertex (graph theory)Vertex cover problem W. H. Freeman and Company ZPP (complexity)♯P ♯P-complete

19 concepts already in your glossary