List of NP-complete problems


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 [ [http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cs/0601002 Minimum Weight Triangulation is NP-Hard, 22nd SCG (2006)] ]
*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) [H. Breu and David G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998]
*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 AS by a collision-free rigid motion of S, and such that both S and AS are connected. ["Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165. ]

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

*Median partition

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

*Timetable design
*Staff scheduling
*Production planning
*Deadlock avoidance

Mathematical programming

Integer 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 GF2|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 hitting set
*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

* Karp's 21 NP-complete problems
* List of PSPACE-complete problems

References

* cite book
last = Garey
first = M.R.
authorlink = Michael Garey
coauthors = Johnson, D.S.
title =
year = 1979
publisher = W.H. Freeman
location = New York
isbn = 0-7167-1045-5
This book is a classic, developing the theory, then cataloguing "many" NP-Complete problems.
* cite conference
last = Cook
first = S.A.
authorlink = Stephen A. Cook
title = The complexity of theorem proving procedures
booktitle = Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York
year = 1971
pages = 151–158
url = http://dx.doi.org/10.1145/800157.805047
doi = 10.1145/800157.805047

* cite web
last = Dunne
first = P.E
title = An annotated list of selected NP-complete problems
publisher = COMP202, Dept. of Computer Science, University of Liverpool
url = http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html
accessdate = 2008-06-21

* cite web
last = Crescenzi
first = P.
coauthors = Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G
title = A compendium of NP optimization problems
publisher = KTH NADA, Stockholm
url = http://www.nada.kth.se/~viggo/problemlist/compendium.html
accessdate = 2008-06-21

* cite web
last = Dahlke
first = K
title = NP-complete problems
work = Math Reference Project
url = http://www.mathreference.com/lan-cx-np,intro.html
accessdate = 2008-06-21

* cite web
first = E
last = Friedman
title = Pearl puzzles are NP-complete
year = 2002
publisher = Stetson University, DeLand, Florida
url = http://www.stetson.edu/~efriedma/papers/pearl/pearl.html
accessdate = 2008-06-21


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • List of PSPACE-complete problems — Here are some of the more commonly known problems that are PSPACE complete when expressed as decision problems. This list is in no way comprehensive. Games and puzzles Generalized versions of: Amazons· Atomix· Geography· Gomoku· Hex· Reversi·… …   Wikipedia

  • Karp's 21 NP-complete problems — One of the most important results in computational complexity theory was Stephen Cook s 1971 demonstration of the first (practically relevant) NP complete problem, the boolean satisfiability problem. [cite book|author = Stephen Cook|year =… …   Wikipedia

  • List of problems — *List of undecidable problems *List of unsolved problems *List of open problems in computer science *List of NP complete problems *List of PSPACE complete problems *List of problems solved by MacGyver …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • List of Camp Lazlo episodes — This is the list of episodes of the Cartoon Network animated series Camp Lazlo. Except where specifically mentioned in the episode synopses, each half hour episode consists of two separately titled segments. Contents 1 Overview 2 Season 1: 2005 3 …   Wikipedia

  • List of schools in Victoria, Australia — This is a list of schools in Victoria, Australia. (NOTE: This list is not complete) Contents 1 Government Primary Schools 1.1 A 1.2 B 1.3 C 1.4 …   Wikipedia

  • List of mathematics articles (K) — NOTOC K K approximation of k hitting set K ary tree K core K edge connected graph K equivalence K factor error K finite K function K homology K means algorithm K medoids K minimum spanning tree K Poincaré algebra K Poincaré group K set (geometry) …   Wikipedia

  • List of World War I books — is an annotated bibliography using APA style citations of a selection of the most useful books on World War I as selected by the editors. Reference books* Ellis, Robert, John, and Mike Cox. The World War I Databook: The Essential Facts and… …   Wikipedia

  • Complete Savages — intertitle Genre Sitcom Created by …   Wikipedia

  • List of rail accidents (1950–1999) — List of rail accidents from 1950 to 1999.For historic accidents before 1950, see List of pre 1950 rail accidents .For accidents from 2000 to the present, see List of rail accidents . notoc 1950s 1950* February 17 1950 ndash; Rockville Centre, New …   Wikipedia