- List of NP-complete problems
Here are some of the more commonly known problems that are

NP-complete when expressed asdecision problem s. 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 asEuclidean 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

*Manymotion 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 game s

*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 forcontext-free grammars

*Covering for linear grammars

*Structural inequivalence forlinear 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.*