.mylinks .toread/work al alg algorithm algorithms algorytmy approximation automata classic complejidad complexity complexitytheory computability computation computer.science computerscience cs math mathematics np np-complete optimization programming research science software tcs
List of NP-complete 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 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.
[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 [4][5]
- Dominating set, a.k.a. domination number [6]
-
- NP-complete special cases include the edge dominating set problem, i.e., the dominating set problem in line graphs. NP-complete 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]
-
- NP-complete 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]
- Two-stage 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]
- Degree-bounded connected subgraph [29]
- Planar subgraph [30]
- Edge-subgraph [31]
- Transitive subgraph [32]
- Uniconnected subgraph [33]
- Minimum k-connected 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 D-morphism [56]
[edit] Miscellaneous
- Path with forbidden pairs [57]
- Multiple choice matching [58]
- Graph Grundy numbering [59]
- Kernel [60]
- K-closure [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
- 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 [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 k-cut
- k-vital 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 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
- 3-dimensional 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
- 3-matroid intersection
[edit] Weighted set problems
- Partition [4]
- 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
[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
- 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 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 Problem
- No-wait flow-shop scheduling
- Two-processor flow-shop with bounded buffer
- Job-shop scheduling
[edit] Miscellaneous
[edit] Mathematical programming
- Integer programming
- 0-1 integer programming [4]
- Quadratic programming (NP-hard in some cases, P if convex)
- Cost-parametric linear programming
- Feasible basis extension
- Minimum weight solution to linear equations
- Open hemisphere
- K-relevancy
- Traveling salesman polytope non-adjacency
- 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
- 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
- Non-linear univariate polynomials over GF[2n], 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
- Square-tiling
- Sudoku
- Tetris
- Variable partition truth assignment
- Verbal arithmetic
[edit] Logic
[edit] Propositional logic
- Satisfiability [4]
- 3-Satisfiability [4]
- 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
[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
- 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] Notes
- ^ 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.
- ^ 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 NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5. 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: 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 NP-complete problems". COMP202, Dept. of Computer Science, University of Liverpool. http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html. Retrieved on 2008-06-21.
- 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 2008-06-21.
- Dahlke, K. "NP-complete problems". Math Reference Project. http://www.mathreference.com/lan-cx-np,intro.html. Retrieved on 2008-06-21.
- Friedman, E (2002). "Pearl puzzles are NP-complete". Stetson University, DeLand, Florida. http://www.stetson.edu/~efriedma/papers/pearl/pearl.html. Retrieved on 2008-06-21.
