.mylinks .toread/work al alg algorithm algorithms algorytmy approximation automata classic complejidad complexity complexitytheory computability computation computer.science computerscience cs math mathematics np npcomplete optimization programming research science software tcs
List of NPcomplete problems
From Wikipedia, the free encyclopedia
This article includes a list of references or external links, but its sources remain unclear because it lacks inline citations. Please improve this article by introducing more precise citations where appropriate. (February 2009) 
Here are some of the more commonly known problems that are NPcomplete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NPcomplete 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 NPCompleteness, and are here presented in the same order and organization.
This list is incomplete; you can help by expanding it.
[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 NPhard.
 Planar partitioning into connected subassemblies: Given a set A of nonoverlapping (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 collisionfree rigid motion of S, and such that both S and A\S are connected. ^{[3]}
[edit] Graph theory
[edit] Covering and partitioning
 Vertex cover ^{[4]}^{[5]}
 Dominating set, a.k.a. domination number ^{[6]}

 NPcomplete special cases include the edge dominating set problem, i.e., the dominating set problem in line graphs. NPcomplete variants include the connected dominating set problem.
 Domatic partition, a.k.a. domatic number ^{[7]}
 Graph coloring, a.k.a. chromatic number ^{[4]}^{[8]}
 Partition into cliques

 This is the same problem as coloring the complement of the given graph^{[9]}.
 Complete coloring, a.k.a. achromatic number ^{[10]}
 Grundy number^{[citation needed]}
 Monochromatic triangle ^{[11]}
 Feedback vertex set ^{[4]}^{[12]}
 Feedback arc set ^{[4]}^{[13]}
 Partial feedback edge set ^{[14]}
 Minimum maximal indepent set a.k.a. minimum independent dominating set ^{[15]}

 NPcomplete special cases include the minimum maximal matching problem,^{[16]} which is essentially equal to the edge dominating set problem (see above).
 Partition into triangles ^{[17]}
 Partition into isomorphic subgraphs ^{[18]}
 Partition into Hamiltonian subgraphs ^{[19]}
 Partition into forests ^{[20]}
 Partition into perfect matchings ^{[21]}
 Twostage maximum weight stochastic matching^{[citation needed]}
 Covering by cliques ^{[4]}^{[22]}
 Berth allocation problem^{[citation needed]}
 Covering by complete bipartite subgraphs ^{[23]}
[edit] Subgraphs and supergraphs
 Clique ^{[4]}^{[24]}
 Independent set ^{[25]}
 Induced subgraph with property Π^{[citation needed]}
 Induced connected subgraph with property Π^{[citation needed]}
 Induced path ^{[26]}
 Balanced complete bipartite subgraph ^{[27]}
 Bipartite subgraph ^{[28]}
 Degreebounded connected subgraph ^{[29]}
 Planar subgraph ^{[30]}
 Edgesubgraph ^{[31]}
 Transitive subgraph ^{[32]}
 Uniconnected subgraph ^{[33]}
 Minimum kconnected subgraph ^{[34]}
 Cubic subgraph ^{[35]}
 Minimum equivalent digraph ^{[36]}
 Hamiltonian completion ^{[37]}
 Interval graph completion ^{[38]}
 Path graph completion ^{[39]}
[edit] Vertex ordering
 Hamiltonian circuit ^{[4]}^{[40]}
 Directed Hamiltonian circuit ^{[4]}^{[41]}
 Hamiltonian path ^{[42]}
 Bandwidth ^{[43]}
 Directed bandwidth ^{[44]}
 Optimal linear arrangement ^{[45]}
 Directed optimal linear arrangement ^{[46]}
 Minimum cut linear arrangement ^{[47]}
 Rooted tree arrangement ^{[48]}
 Directed elimination ordering ^{[49]}
 Elimination degree sequence ^{[50]}
[edit] Iso and other morphisms
 Subgraph isomorphism ^{[51]}
 Largest common subgraph ^{[52]}
 Maximum subgraph matching ^{[53]}
 Graph contractability ^{[54]}
 Graph homomorphism ^{[55]}
 Digraph Dmorphism ^{[56]}
[edit] Miscellaneous
 Path with forbidden pairs ^{[57]}
 Multiple choice matching ^{[58]}
 Graph Grundy numbering ^{[59]}
 Kernel ^{[60]}
 Kclosure ^{[61]}
 Intersection graph basis ^{[62]}
 Path distinguishers ^{[63]}
 Metric dimension ^{[64]}
 Nesetril–Rödl dimension ^{[65]}
 Threshold number ^{[66]}
 Oriented diameter ^{[67]}
 Weighted diameter ^{[68]}
[edit] Network design
[edit] Spanning trees
 Degreeconstrained 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 ^{[4]}
 Geometric Steiner tree
 Cable Trench Problem
 Minimum Touching Tree/Minimum Length Corridor
[edit] Cuts and connectivity
 Graph partitioning
 Acyclic partition
 Maximum cut ^{[4]}
 Minimum cut into bounded sets
 Biconnectivity augmentation
 Strong connectivity augmentation
 Network reliability
 Network survivability
 Multiway Cut
 Minimum kcut
 kvital edges
[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 weightconstrained path
 Stackercrane
 Time constrained traveling salesman feasibility
 Traveling salesman problem
 Vehicle routing problem
[edit] Flow problems
 Minimum edgecost flow
 Integral flow with multipliers
 Path constrained network flow
 Integral flow with homologous arcs
 Integral flow with bundles
 Undirected flow with lower bounds
 Directed twocommodity integral flow
 Undirected twocommodity integral flow
 Disjoint connecting paths
 Maximum lengthbounded disjoint paths
 Maximum fixedlength 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
 Minmax multicenter
 Minsum multicenter
 Uncapacitated Facility Location
 Metric kcenter
[edit] Sets and partitions
[edit] Covering, hitting, and splitting
 3dimensional matching ^{[4]}
 Exact cover ^{[4]}
 Set packing ^{[4]}
 Set splitting
 Set cover ^{[4]}
 Minimum test set
 Set basis
 Hitting set ^{[4]}
 Intersection pattern
 Comparative containment
 3matroid intersection
[edit] Weighted set problems
 Partition ^{[4]}
 Subset sum
 Subset product
 3partition
 Numerical 3dimensional matching
 Numerical matching with target sums
 Expected component sum
 Minimum sum of squares
 Kth largest subset
 Kth largest mtuple
[edit] Set partitions
[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
 2dimensional consecutive sets
 Stringtostring correction
 Grouping by swapping
 External macro data compression
 Internal macro data compression
 Regular expression substitution
 Rectilinear picture compression
 Optimal vector quantization codebook
 Minimal grammarbased compression
 Adaptive Blocksize Compression
[edit] Database problems
 Minimum cardinality key
 Additional key
 Prime attribute name
 BoyceCodd 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
 Job sequencing ^{[4]}
 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 setup 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
 Openshop scheduling
 Flow Shop Scheduling Problem
 Nowait flowshop scheduling
 Twoprocessor flowshop with bounded buffer
 Jobshop scheduling
[edit] Miscellaneous
[edit] Mathematical programming
 Integer programming
 01 integer programming ^{[4]}
 Quadratic programming (NPhard in some cases, P if convex)
 Costparametric linear programming
 Feasible basis extension
 Minimum weight solution to linear equations
 Open hemisphere
 Krelevancy
 Traveling salesman polytope nonadjacency
 Knapsack ^{[4]}
 Integer knapsack
 Continuous multiple choice knapsack
 Partially ordered knapsack
 Generalized assignment problem
 Comparative vector inequalities
 Sparse approximation
[edit] Algebra and number theory
[edit] Divisibility problems
 Quadratic congruences
 Simultaneous incongruences
 Simultaneous divisibility of linear polynomials
 Comparative divisibility
 Exponential expression divisibility
 Nondivisibility of a product polynomial
 Nontrivial 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
 Nonlinear univariate polynomials over GF[2^{n}], n the length of the input.
[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
 Alternating maximum weighted matching
 Annihilation
 Battleship
 Clickomania (SameGame)
 Cross Sums
 Crossword puzzle construction
 Fillomino^{[citation needed]}
 FreeCell
 Heyawake^{[citation needed]}
 Instant Insanity
 Kakuro
 Light Up
 LITS
 Mastermind
 Masyu
 Minesweeper Consistency Problem
 Nurikabe
 Paint by numbers (Nonogram)
 Rabin games
 Sift
 Slither Link
 Squaretiling
 Sudoku
 Tetris
 Variable partition truth assignment
 Verbal arithmetic
[edit] Logic
[edit] Propositional logic
 Satisfiability ^{[4]}
 3Satisfiability ^{[4]}
 Notallequal 3SAT
 Oneinthree 3SAT
 Maximum 3Satisfiability
 Generalized satisfiability
 Nontautology
 Minimum disjunctive normal form
 Truthfunctionally complete connectives
 Planar3SAT
 Monotone3SAT
[edit] Miscellaneous
 Modal logic S5Satisfiability
 Negationfree logic
 Conjunctive satisfiability with functions and inequalities
 Minimum axiom set
 First order subsumption
 Second order instantiation
[edit] Automata and language theory
[edit] Automata theory
 Twoway finite state automaton nonemptiness
 Quasirealtime automaton acceptance
 Reduction of incompletely specified automata
 Minimum inferred finite state automaton
[edit] Formal languages
 Minimum inferred regular expression
 Reynolds covering for contextfree grammars
 Covering for linear grammars
 Structural inequivalence for linear grammars
 Regular grammar inequivalence
 NonLR(K) contextfree grammar
 Etol grammar nonemptiness
 Contextfree programmed language membership
 Quasirealtime 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 oneregister 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
 Noncontainment for free Bschemes
 Nonfreedom for loopfree program schemes
 Programs with formally recursive procedures
[edit] Miscellaneous
 Cyclic ordering
 Nonliveness of free choice Petri nets
 Reachability for 1conservative Petri nets
 Finite function generation
 Permutation generation
 Decoding of linear codes
 ShapleyShubik 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] Notes
 ^ Minimum Weight Triangulation is NPHard, 22nd SCG (2006)
 ^ H. Breu and David G. Kirkpatrick. "Unit Disk Graph Recognition is NPhard." Comput. Geom. Theory Appl., 9(12):324, 1998
 ^ "Assembly Into Two Connected Parts Is NPComplete", Inf. Proc. Letters 55 (1995), 159165.
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} ^{h} ^{i} ^{j} ^{k} ^{l} ^{m} ^{n} ^{o} ^{p} ^{q} ^{r} ^{s} ^{t} ^{u} Karp (1972)
 ^ Garey–Johnson: GT1
 ^ Garey–Johnson: GT2
 ^ Garey–Johnson: GT3
 ^ Garey–Johnson: GT4
 ^ Garey–Johnson: GT15
 ^ Garey–Johnson: GT5
 ^ Garey–Johnson: GT6
 ^ Garey–Johnson: GT7
 ^ Garey–Johnson: GT8
 ^ Garey–Johnson: GT9
 ^ Minimum Independent Dominating Set
 ^ Garey–Johnson: GT10
 ^ Garey–Johnson: GT11
 ^ Garey–Johnson: GT12
 ^ Garey–Johnson: GT13
 ^ Garey–Johnson: GT14
 ^ Garey–Johnson: GT16
 ^ Garey–Johnson: GT17
 ^ Garey–Johnson: GT18
 ^ Garey–Johnson: GT19
 ^ Garey–Johnson: GT20
 ^ Garey–Johnson: GT23
 ^ Garey–Johnson: GT24
 ^ Garey–Johnson: GT25
 ^ Garey–Johnson: GT26
 ^ Garey–Johnson: GT27
 ^ Garey–Johnson: GT28
 ^ Garey–Johnson: GT29
 ^ Garey–Johnson: GT30
 ^ Garey–Johnson: GT31
 ^ Garey–Johnson: GT32
 ^ Garey–Johnson: GT33
 ^ Garey–Johnson: GT34
 ^ Garey–Johnson: GT35
 ^ Garey–Johnson: GT36
 ^ Garey–Johnson: GT37
 ^ Garey–Johnson: GT38
 ^ Garey–Johnson: GT39
 ^ Garey–Johnson: GT40
 ^ Garey–Johnson: GT41
 ^ Garey–Johnson: GT42
 ^ Garey–Johnson: GT43
 ^ Garey–Johnson: GT44
 ^ Garey–Johnson: GT45
 ^ Garey–Johnson: GT46
 ^ Garey–Johnson: GT47
 ^ Garey–Johnson: GT48
 ^ Garey–Johnson: GT49
 ^ Garey–Johnson: GT50
 ^ Garey–Johnson: GT51
 ^ Garey–Johnson: GT52
 ^ Garey–Johnson: GT53
 ^ Garey–Johnson: GT54
 ^ Garey–Johnson: GT55
 ^ Garey–Johnson: GT56
 ^ Garey–Johnson: GT57
 ^ Garey–Johnson: GT58
 ^ Garey–Johnson: GT59
 ^ Garey–Johnson: GT60
 ^ Garey–Johnson: GT61
 ^ Garey–Johnson: GT62
 ^ Garey–Johnson: GT63
 ^ Garey–Johnson: GT64
 ^ Garey–Johnson: GT65
[edit] References
 Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NPCompleteness. New York: W.H. Freeman. ISBN 0716710455. This book is a classic, developing the theory, then cataloguing many NPComplete problems.
 Cook, S.A. (1971). "The complexity of theorem proving procedures". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York: 151–158. doi:10.1145/800157.805047.
 Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, Raymond E.; Thatcher, James W., Complexity of Computer Computations, Plenum, pp. 85–103
 Dunne, P.E. "An annotated list of selected NPcomplete problems". COMP202, Dept. of Computer Science, University of Liverpool. http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html. Retrieved on 20080621.
 Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. "A compendium of NP optimization problems". KTH NADA, Stockholm. http://www.nada.kth.se/~viggo/problemlist/compendium.html. Retrieved on 20080621.
 Dahlke, K. "NPcomplete problems". Math Reference Project. http://www.mathreference.com/lancxnp,intro.html. Retrieved on 20080621.
 Friedman, E (2002). "Pearl puzzles are NPcomplete". Stetson University, DeLand, Florida. http://www.stetson.edu/~efriedma/papers/pearl/pearl.html. Retrieved on 20080621.