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

Vertex cover · Dominating set · Domatic number · Graph k-colorability · Achromatic 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 · Covering by complete bipartite subgraphs

[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

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

[edit] Iso- and other morphisms

Subgraph isomorphism · Largest common subgraph · Maximum subgraph matching · Graph contractability · Graph homomorphism · Digraph D-morphism

[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

[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

[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

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

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

[edit] Database problems

Minimum cardinality key · Additional key · Prime attribute name · Boyce-Codd normal form violation · Conjunctive query foldability · Conjunctive boolean 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 · 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

[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

[edit] Games and puzzles

Rabin games · Variable partition truth assignment · Sift · Alternating hitting set · Alternating maximum weighted matching · Annihilation · Left-right Hackenbush for Redwood furniture · Square-tiling · Crossword puzzle construction · Generalized Instant Insanity · Minesweeper Consistency Problem · Sudoku · Nurikabe · Paint by numbers · Light Up · Slither Link · Cross Sums · Clickomania · Tetris · Mastermind · Masyu · Battleship . FreeCell

[edit] Logic

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

[edit] Miscellaneous

First order theory of equality · Modal logic S5-Satisfiability · Modal logic provability · 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 D. 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.
Retrieved from "http://en.wikipedia.org../../../l/i/s/List_of_NP-complete_problems_d747.html"
In other languages