List of NP-complete problems
Here are some of the more commonly known problems that are NP-complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP-complete problems). Most of the problems in this list are taken from Garey and Johnson's seminal book Computers and Intractability: A Guide to the Theory of NP-Completeness, and are here presented in the same order and organization.
 |
Computational geometry
- Minimum weight triangulation for a set of points in the plane [1]
- Testing whether a tree may be represented as Euclidean minimum spanning tree
- Unit disk graph recognition (Unit disk graphs are intersection graphs of circles of unit radius in the plane)[2]
- Many motion planning among polygonal obstacles in the plane are NP-hard.
- Planar partitioning into connected subassemblies: Given a set A of non-overlapping (but possibly touching) polygons in the plane, decide if there is a proper subset S of A that can be separated from A\S by a collision-free rigid motion of S, and such that both S and A\S are connected. [3]
Graph theory
Covering and partitioning
- Vertex cover
- Dominating set
- Domatic number
- Graph k-colorability
- Achromatic number
- Grundy number
- Monochromatic triangle
- Feedback vertex set
- Feedback arc set
- Partial feedback edge set
- Minimum maximal matching
- Partition into triangles
- Partition into isomorphic subgraphs
- Partition into Hamiltonian subgraphs
- Partition into forests
- Partition into cliques
- Partition into perfect matchings
- Two-stage maximum weight stochastic matching
- Covering by cliques
- Berth Allocation Problem (BAP)
- Covering by complete bipartite subgraphs
Subgraphs and supergraphs
- Clique
- Independent set
- Induced subgraph with property Pi
- Induced connected subgraph with property Pi
- Induced path
- Balanced complete bipartite subgraph
- Bipartite subgraph
- Degree-bounded connected subgraph
- Planar subgraph
- Edge-subgraph
- Transitive subgraph
- Uniconnected subgraph
- Minimum k-connected subgraph
- Cubic subgraph
- Minimum equivalent digraph
- Hamiltonian completion
- Interval graph completion
- Path graph completion
Vertex ordering
- Hamiltonian circuit
- Directed Hamiltonian circuit
- Hamiltonian path
- Bandwidth
- Directed bandwidth
- Optimal linear arrangement
- Directed optimal linear arrangement
- Minimum cut linear arrangement
- Rooted tree arrangement
- Directed elimination ordering
- Elimination degree sequence
Iso- and other morphisms
- Subgraph isomorphism
- Largest common subgraph
- Maximum subgraph matching
- Graph contractability
- Graph homomorphism
- Digraph D-morphism
Miscellaneous
- Path with forbidden pairs
- Multiple choice matching
- Graph Grundy numbering
- Kernel
- K-closure
- Intersection graph basis
- Path distinguishers
- Metric dimension
- Nesetril-Rödl dimension
- Threshold number
- Oriented diameter
- Weighted diameter
Network design
Spanning trees
- Degree-constrained spanning tree
- Minimum degree spanning tree
- Maximum leaf spanning tree
- Shortest total path length spanning tree
- Bounded diameter spanning tree
- Capacitated spanning tree
- Geometric capacitated spanning tree
- Optimum communication spanning tree
- Isomorphic spanning tree
- Kth best spanning tree
- Bounded component spanning forest
- Multiple choice branching
- Steiner tree
- Geometric Steiner tree
- Cable Trench Problem
- Minimum Touching Tree/Minimum Length Corridor
Cuts and connectivity
- Graph partitioning
- Acyclic partition
- Max weight cut
- Minimum cut into bounded sets
- Biconnectivity augmentation
- Strong connectivity augmentation
- Network reliability
- Network survivability
- Multiway Cut
- Minimum k-cut
Routing problems
- Bottleneck traveling salesman
- Chinese postman for mixed graphs
- Euclidean traveling salesman
- K most vital arcs
- Kth shortest path
- Metric traveling salesman
- Longest circuit
- Longest path
- Prize Collecting Traveling Salesman
- Rural Postman
- Shortest path in general networks
- Shortest weight-constrained path
- Stacker-crane
- Time constrained traveling salesman feasibility
- Traveling salesman problem
- Vehicle routing problem
Flow problems
- Minimum edge-cost flow
- Integral flow with multipliers
- Path constrained network flow
- Integral flow with homologous arcs
- Integral flow with bundles
- Undirected flow with lower bounds
- Directed two-commodity integral flow
- Undirected two-commodity integral flow
- Disjoint connecting paths
- Maximum length-bounded disjoint paths
- Maximum fixed-length disjoint paths
- Unsplittable multicommodity flow
Miscellaneous
- Quadratic assignment problem
- Minimizing dummy activities in PERT networks
- Constrained triangulation
- Intersection graph for segments on a grid
- Edge embedding on a grid
- Geometric connected dominating set
- Minimum broadcast time
- Min-max multicenter
- Min-sum multicenter
- Uncapacitated Facility Location
- Metric k-center
Sets and partitions
Covering, hitting, and splitting
- 3-dimensional matching
- Exact cover
- Set packing
- Set splitting
- Set cover
- Minimum test set
- Set basis
- Hitting set
- Intersection pattern
- Comparative containment
- 3-matroid intersection
Weighted set problems
- Partition
- Subset sum
- Subset product
- 3-partition
- Numerical 3-dimensional matching
- Numerical matching with target sums
- Expected component sum
- Minimum sum of squares
- Kth largest subset
- Kth largest m-tuple
Set partitions
Storage and retrieval
Data storage
- Bin packing
- Dynamic storage allocation
- Pruned trie space minimization
- Expected retrieval cost
- Rooted tree storage assignment
- Multiple copy file allocation
- Capacity assignment
Compression and representation
- Shortest common supersequence
- Shortest common superstring
- Longest common subsequence problem for the case of arbitrary (i.e., not a priori fixed) number of input sequences even in the case of the binary alphabet
- Bounded post correspondence problem
- Hitting string
- Sparse matrix compression
- Consecutive ones submatrix
- Consecutive ones matrix partition
- Consecutive ones matrix augmentation
- Consecutive block minimization
- Consecutive sets
- 2-dimensional consecutive sets
- String-to-string correction
- Grouping by swapping
- External macro data compression
- Internal macro data compression
- Regular expression substitution
- Rectilinear picture compression
- Optimal vector quantization codebook
- Minimal grammar-based compression
- Adaptive Block-size Compression
Database problems
- Minimum cardinality key
- Additional key
- Prime attribute name
- Boyce-Codd normal form violation
- Conjunctive query foldability
- Boolean conjunctive query
- Tableau equivalence
- Serializability of database histories
- Safety of database transaction systems
- Consistency of database frequency tables
- Safety of file protection systems
Sequencing and scheduling
Sequencing on one processor
- Sequencing with release times and deadlines
- Sequencing to minimize Tardy tasks
- Sequencing to minimize Tardy weight
- Sequencing to minimize weighted completion time
- Sequencing to minimize weighted tardiness
- Sequencing with deadlines and set-up times
- Sequencing to minimize maximum cumulative cost
Multiprocessor scheduling
- Multiprocessor scheduling
- Precedence constrained scheduling
- Resource constrained scheduling
- Scheduling with individual deadlines
- Preemptive scheduling
- Scheduling to minimize weighted completion time
Shop scheduling
- Open-shop scheduling
- Flow-shop scheduling
- No-wait flow-shop scheduling
- Two-processor flow-shop with bounded buffer
- Job-shop scheduling
Miscellaneous
Mathematical programming
- 0-1 Integer programming
- Quadratic programming (NP-hard in some cases, P when convex)
- Cost-parametric linear programming
- Feasible basis extension
- Minimum weight solution to linear equations
- Open hemisphere
- K-relevancy
- Traveling salesman polytope non-adjacency
- Knapsack
- Integer knapsack
- Continuous multiple choice knapsack
- Partially ordered knapsack
- Generalized assignment problem
- Comparative vector inequalities
- Sparse approximation
Algebra and number theory
Divisibility problems
- Quadratic congruences
- Simultaneous incongruences
- Simultaneous divisibility of linear polynomials
- Comparative divisibility
- Exponential expression divisibility
- Non-divisibility of a product polynomial
- Non-trivial greatest common divisor
Solvability of equations
- Quadratic diophantine equations
- Algebraic equations over GF[2]
- Root of modulus 1
- Number of roots for a product polynomial
- Periodic solution recurrence relation
Miscellaneous
- Permanent evaluation
- Cosine product integration
- Equilibrium point
- Unification with commutative operators
- Unification for finitely presented algebras
- Integer expression membership
- Minimal addition chain
Games and puzzles
- Alternating maximum weighted matching
- Annihilation
- Battleship
- Clickomania (SameGame)
- Cross Sums
- Crossword puzzle construction
- FreeCell
- Instant Insanity
- Light Up
- LITS
- Mastermind
- Masyu
- Minesweeper Consistency Problem
- Nurikabe
- Paint by numbers (Nonogram)
- Rabin games
- Sift
- Slither Link
- Square-tiling
- Sudoku
- Tetris
- Variable partition truth assignment
- Verbal arithmetic
Logic
Propositional logic
- Satisfiability
- 3-Satisfiability
- Not-all-equal 3SAT
- One-in-three 3SAT
- Maximum 3-Satisfiability
- Generalized satisfiability
- Non-tautology
- Minimum disjunctive normal form
- Truth-functionally complete connectives
- Planar-3SAT
- Monotone-3SAT
Miscellaneous
- Modal logic S5-Satisfiability
- Negation-free logic
- Conjunctive satisfiability with functions and inequalities
- Minimum axiom set
- First order subsumption
- Second order instantiation
Automata and language theory
Automata theory
- Two-way finite state automaton non-emptiness
- Quasi-realtime automaton acceptance
- Reduction of incompletely specified automata
- Minimum inferred finite state automaton
Formal languages
- Minimum inferred regular expression
- Reynolds covering for context-free grammars
- Covering for linear grammars
- Structural inequivalence for linear grammars
- Regular grammar inequivalence
- Non-LR(K) context-free grammar
- Etol grammar non-emptiness
- Context-free programmed language membership
- Quasi-real-time language membership
- Etol language membership
- Tree transducer language membership
Program optimization
Code generation
- Register sufficiency
- Feasible register assignment
- Register sufficiency for loops
- Code generation on a one-register machine
- Code generation with unlimited registers
- Code generation for parallel assignments
- Code generation with address expressions
- Code generation with unfixed variable locations
- Ensemble computation
- Microcode bit optimization
Programs and schemes
- Inequivalence of programs with arrays
- Inequivalence of programs with assignments
- Inequivalence of finite memory programs
- Inequivalence of loop programs without nesting
- Inequivalence of simple functions
- Strong inequivalence of Ianov schemes
- Strong inequivalence for monadic recursion
- Non-containment for free B-schemes
- Non-freedom for loop-free program schemes
- Programs with formally recursive procedures
Miscellaneous
- Cyclic ordering
- Non-liveness of free choice Petri nets
- Reachability for 1-conservative Petri nets
- Finite function generation
- Permutation generation
- Decoding of linear codes
- Shapley-Shubik voting power
- Clustering
- Randomization test for matched pairs
- Maximum likelihood ranking
- Matrix domination
- Matrix cover
- Simply deviated disjunction
- Decision tree
- Minimum weight and/or graph solution
- Fault detection in logic circuits
- Fault detection in directed graphs
- Fault detection with test points
See also
References
- ^ Minimum Weight Triangulation is NP-Hard, 22nd SCG (2006)
- ^ H. Breu and David G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998
- ^ "Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165.
- Garey, M.R. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5.
{{cite book}}: Unknown parameter|coauthors=ignored (|author=suggested) (help) This book is a classic, developing the theory, then cataloguing many NP-Complete problems. - Cook, S.A. (1971). "The complexity of theorem proving procedures". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. pp. 151–158. doi:10.1145/800157.805047.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help) - Dunne, P.E. "An annotated list of selected NP-complete problems". COMP202, Dept. of Computer Science, University of Liverpool. Retrieved 2008-06-21.
- Crescenzi, P. "A compendium of NP optimization problems". KTH NADA, Stockholm. Retrieved 2008-06-21.
{{cite web}}: Unknown parameter|coauthors=ignored (|author=suggested) (help) - Dahlke, K. "NP-complete problems". Math Reference Project. Retrieved 2008-06-21.
- Friedman, E (2002). "Pearl puzzles are NP-complete". Stetson University, DeLand, Florida. Retrieved 2008-06-21.