List of NP-complete problems

From Wikipedia, the free encyclopedia

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.

This list is incomplete; you can help by expanding it.

Contents

[edit] 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]

[edit] Graph theory

[edit] Covering and partitioning

[edit] 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

[edit] Vertex ordering

[edit] Iso- and other morphisms

[edit] 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

[edit] Network design

[edit] Spanning trees

  • Degree-constrained 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

[edit] 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

[edit] 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

[edit] 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

[edit] 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

[edit] Sets and partitions

[edit] Covering, hitting, and splitting

[edit] 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

[edit] Set partitions

  • Median partition

[edit] Storage and retrieval

[edit] Data storage

  • Bin packing
  • Dynamic storage allocation
  • Pruned trie space minimization
  • Expected retrieval cost
  • Rooted tree storage assignment
  • Multiple copy file allocation
  • Capacity assignment

[edit] 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

[edit] 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

[edit] Sequencing and scheduling

[edit] 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

[edit] Multiprocessor scheduling

  • Multiprocessor scheduling
  • Precedence constrained scheduling
  • Resource constrained scheduling
  • Scheduling with individual deadlines
  • Preemptive scheduling
  • Scheduling to minimize weighted completion time

[edit] Shop scheduling

  • Open-shop scheduling
  • Flow-shop scheduling
  • No-wait flow-shop scheduling
  • Two-processor flow-shop with bounded buffer
  • Job-shop scheduling

[edit] Miscellaneous

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

[edit] Mathematical programming

Integer programming

[edit] Algebra and number theory

[edit] 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

[edit] 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

[edit] Miscellaneous

  • Permanent evaluation
  • Cosine product integration
  • Equilibrium point
  • Unification with commutative operators
  • Unification for finitely presented algebras
  • Integer expression membership
  • Minimal addition chain

[edit] Games and puzzles

Alternating hitting set

[edit] Logic

[edit] Propositional logic

[edit] Miscellaneous

  • Modal logic S5-Satisfiability
  • Negation-free logic
  • Conjunctive satisfiability with functions and inequalities
  • Minimum axiom set
  • First order subsumption
  • Second order instantiation

[edit] Automata and language theory

[edit] Automata theory

  • Two-way finite state automaton non-emptiness
  • Quasi-realtime automaton acceptance
  • Reduction of incompletely specified automata
  • Minimum inferred finite state automaton

[edit] Formal languages

  • Regular expression inequivalence
  • 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

[edit] Program optimization

[edit] 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

[edit] 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

[edit] 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

[edit] See also

[edit] References

  1. ^ Minimum Weight Triangulation is NP-Hard, 22nd SCG (2006)
  2. ^ H. Breu and David G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998
  3. ^ "Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165.
Languages