List of NP-complete problems

风住尘香花已尽,日晚倦梳头。物事人非事事休,欲语泪先流。闻说双溪春尚好,也拟泛轻舟。只恐双溪舴艋舟,载不动,许多愁。
打印 被阅读次数

List of NP-complete problems

From Wikipedia, the free encyclopedia

Jump to: navigation, search

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.

Contents

[hide]

[edit] Computational geometry

[edit] Graph theory

[edit] Covering and partitioning

[edit] Subgraphs and supergraphs

[edit] Vertex ordering

[edit] Iso- and other morphisms

[edit] Miscellaneous

[edit] Network design

[edit] Spanning trees

[edit] Cuts and connectivity

[edit] Routing problems

[edit] Flow problems

[edit] Miscellaneous

[edit] Sets and partitions

[edit] Covering, hitting, and splitting

[edit] Weighted set problems

[edit] Set partitions

[edit] Storage and retrieval

[edit] Data storage

[edit] Compression and representation

. 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

[edit] Database problems

[edit] Sequencing and scheduling

[edit] Sequencing on one processor

[edit] Multiprocessor scheduling

[edit] Shop scheduling

[edit] Miscellaneous

[edit] Mathematical programming

Integer programming

[edit] Algebra and number theory

[edit] Divisibility problems

[edit] Solvability of equations

[edit] Miscellaneous

[edit] Games and puzzles

Alternating hitting set

[edit] Logic

[edit] Propositional logic

[edit] Miscellaneous

[edit] Automata and language theory

[edit] Automata theory

[edit] Formal languages

[edit] Program optimization

[edit] Code generation

[edit] Programs and schemes

[edit] Miscellaneous

[edit] See also

[edit] 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.
登录后才可评论.