List of NP-complete problems

From Wikipedia, the free encyclopedia

Categories: Incomplete lists | Mathematics-related lists | NP-complete problems

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.

1 Computational geometry
2 Graph theory
3 Network design
4 Sets and partitions
5 Storage and retrieval
6 Sequencing and scheduling
7 Mathematical programming
8 Algebra and number theory
9 Games and puzzles
10 Logic
- 10.1 Propositional logic
- 10.2 Miscellaneous
11 Automata and language theory
- 11.1 Automata theory
- 11.2 Formal languages
12 Program optimization
- 12.1 Code generation
- 12.2 Programs and schemes
13 Miscellaneous
14 See also
15 References

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]
      Graph theory
      
      Covering and partitioning
      Subgraphs and supergraphs
      Vertex ordering
      Iso- and other morphisms
      Miscellaneous
      Network design
      
      Spanning trees
      Cuts and connectivity
      Routing problems
      Flow problems
      Miscellaneous
      Sets and partitions
      
      Covering, hitting, and splitting
      Weighted set problems
      Set partitions
      - Median partition
      Storage and retrieval
      
      Data storage
      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
      Database problems
      Sequencing and scheduling
      
      Sequencing on one processor
      Multiprocessor scheduling
      Shop scheduling
      Miscellaneous
      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
      Algebra and number theory
      
      Divisibility problems
      Solvability of equations
      Miscellaneous
      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 games
      - 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
      - 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
      Program optimization
      
      Code generation
      Programs and schemes
      Miscellaneous
      See also
      - Karp's 21 NP-complete problems
      - List of PSPACE-complete problems
      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.
      - M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman. 1983. ISBN 0-7167-1045-5.
      - Erich Friedman. "Pearl Puzzles are NP-Complete". In preparation. 2002. [1].
      - Paul E. Dunne. An Annotated List of Selected NP-complete Problems. The University of Liverpool, Dept of Computer Science, COMP202.
      - Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger. A compendium of NP optimization problems. KTH NADA. Stockholm.fr:Liste de problèmes NP-complets
      pl:Lista problemów NP-zupełnych

Retrieved from "http://en.wikilib.com/wiki/List_of_NP-complete_problems"

Personal tools

List of NP-complete problems

From Wikipedia, the free encyclopedia

Contents

Computational geometry

Graph theory

Covering and partitioning

Subgraphs and supergraphs

Vertex ordering

Iso- and other morphisms

Miscellaneous

Network design

Spanning trees

Cuts and connectivity

Routing problems

Flow problems

Miscellaneous

Sets and partitions

Covering, hitting, and splitting

Weighted set problems

Set partitions

Storage and retrieval

Data storage

Compression and representation

Database problems

Sequencing and scheduling

Sequencing on one processor

Multiprocessor scheduling

Shop scheduling

Miscellaneous

Mathematical programming

Algebra and number theory

Divisibility problems

Solvability of equations

Miscellaneous

Games and puzzles

Logic

Propositional logic

Miscellaneous

Automata and language theory

Automata theory

Formal languages

Program optimization

Code generation

Programs and schemes

Miscellaneous

See also

References

Views

Navigation

Search

Toolbox

AD Links