» 
Arabic Bulgarian Chinese Croatian Czech Danish Dutch English Estonian Finnish French German Greek Hebrew Hindi Hungarian Icelandic Indonesian Italian Japanese Korean Latvian Lithuanian Malagasy Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swedish Thai Turkish Vietnamese
Arabic Bulgarian Chinese Croatian Czech Danish Dutch English Estonian Finnish French German Greek Hebrew Hindi Hungarian Icelandic Indonesian Italian Japanese Korean Latvian Lithuanian Malagasy Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swedish Thai Turkish Vietnamese

definition - list of np-complete problems

definition of Wikipedia

   Advertizing ▼

Wikipedia

List of 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.

Contents

  Graph theory

  Covering and partitioning

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.
This is the same problem as coloring the complement of the given graph.[6]
NP-complete special cases include the minimum maximal matching problem,[13] which is essentially equal to the edge dominating set problem (see above).

  Subgraphs and supergraphs

  Vertex ordering

  Iso- and other morphisms

  Miscellaneous

  Network design

  Spanning trees

  Cuts and connectivity

  Routing problems

  Flow problems

  Miscellaneous

  Graph Drawing

Graphs occur frequently in everyday applications, and are used to model a lot of often huge data. Such examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (see e.g. Facebook or LinkedIn). Therefore, even when all information is available in the form of a graph, it is important to have good ways of visualizing the data in order to make sense of it and extract interesting features, and this is what makes graph drawing important.

  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

  • Job sequencing[1]
  • 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

  Shop scheduling

  Miscellaneous

  Mathematical programming

  Algebra and number theory

  Divisibility problems

  Solvability of equations

  Miscellaneous

  Games and puzzles

  Logic

  Propositional logic

Propositional logic problems, in particular satisfiability problems and their variants, are of particular practical interest because many practical problems can be solved by expressing them as satisfiability problems, and then using efficient SAT solvers to obtain an exact solution quickly[citation needed].

  Miscellaneous

  Automata and language theory

  Automata theory

  Formal languages

  Computational geometry

  • 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)[142]
  • 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.[143]
  • Art gallery problem and its variations.

  Program optimization

  Code generation

  Programs and schemes

  Miscellaneous

  See also

  Notes

  1. ^ a b c d e f g h i j k l m n o p q r s t u Karp (1972)
  2. ^ Garey & Johnson (1979): GT1
  3. ^ Garey & Johnson (1979): GT2
  4. ^ Garey & Johnson (1979): GT3
  5. ^ Garey & Johnson (1979): GT4
  6. ^ Garey & Johnson (1979): GT15
  7. ^ Garey & Johnson (1979): GT5
  8. ^ Garey & Johnson (1979): GT6
  9. ^ Garey & Johnson (1979): GT7
  10. ^ Garey & Johnson (1979): GT8
  11. ^ Garey & Johnson (1979): GT9
  12. ^ Minimum Independent Dominating Set
  13. ^ Garey & Johnson (1979): GT10
  14. ^ Garey & Johnson (1979): GT11
  15. ^ Garey & Johnson (1979): GT12
  16. ^ Garey & Johnson (1979): GT13
  17. ^ Garey & Johnson (1979): GT14
  18. ^ Garey & Johnson (1979): GT16
  19. ^ Garey & Johnson (1979): GT17
  20. ^ Garey & Johnson (1979): GT18
  21. ^ a b Garey & Johnson (1979): GT56
  22. ^ a b Arnborg, Corneil & Proskurowski (1987)
  23. ^ Garey & Johnson (1979): GT19
  24. ^ Garey & Johnson (1979): GT20
  25. ^ Garey & Johnson (1979): GT23
  26. ^ Garey & Johnson (1979): GT24
  27. ^ Garey & Johnson (1979): GT25
  28. ^ Garey & Johnson (1979): GT26
  29. ^ Garey & Johnson (1979): GT27
  30. ^ Garey & Johnson (1979): GT28
  31. ^ Garey & Johnson (1979): GT29
  32. ^ Garey & Johnson (1979): GT30
  33. ^ Garey & Johnson (1979): GT31
  34. ^ Garey & Johnson (1979): GT32
  35. ^ Garey & Johnson (1979): GT33
  36. ^ Garey & Johnson (1979): GT34
  37. ^ Garey & Johnson (1979): GT35
  38. ^ Garey & Johnson (1979): GT36
  39. ^ Garey & Johnson (1979): GT37
  40. ^ Garey & Johnson (1979): GT38
  41. ^ Garey & Johnson (1979): GT39
  42. ^ Garey & Johnson (1979): GT40
  43. ^ Garey & Johnson (1979): GT41
  44. ^ Garey & Johnson (1979): GT42
  45. ^ Garey & Johnson (1979): GT43
  46. ^ Garey & Johnson (1979): GT44
  47. ^ Garey & Johnson (1979): GT45
  48. ^ Garey & Johnson (1979): GT46
  49. ^ Garey & Johnson (1979): GT47
  50. ^ Kashiwabara & Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981).
  51. ^ Garey & Johnson (1979): GT48
  52. ^ Garey & Johnson (1979): GT49
  53. ^ Garey & Johnson (1979): GT50
  54. ^ Garey & Johnson (1979): GT51
  55. ^ Garey & Johnson (1979): GT52
  56. ^ Garey & Johnson (1979): GT53
  57. ^ Garey & Johnson (1979): GT54
  58. ^ Garey & Johnson (1979): GT55
  59. ^ Garey & Johnson (1979): GT57
  60. ^ Garey & Johnson (1979): GT58
  61. ^ Garey & Johnson (1979): GT59
  62. ^ Garey & Johnson (1979): GT60
  63. ^ Garey & Johnson (1979): GT61
  64. ^ Garey & Johnson (1979): GT62
  65. ^ Garey & Johnson (1979): GT63
  66. ^ Garey & Johnson (1979): GT64
  67. ^ Garey & Johnson (1979): GT65
  68. ^ "Normalized Cuts and Image Segmentation". IEEE. 20 October 2009. http://www.cs.berkeley.edu/~malik/papers/SM-ncut.pdf. 
  69. ^ a b "On the computational complexity of upward and rectilinear planarity testing". Lecture Notes in Computer Science. 894/1995. 1995. pp. 286–297. DOI:10.1007/3-540-58950-3_384. 
  70. ^ Garey & Johnson (1979): SP1
  71. ^ Garey & Johnson (1979): SP2
  72. ^ Garey & Johnson (1979): SP3
  73. ^ Garey & Johnson (1979): SP4
  74. ^ Garey & Johnson (1979): SP5
  75. ^ Garey & Johnson (1979): SP6
  76. ^ Garey & Johnson (1979): SP7
  77. ^ Garey & Johnson (1979): SP8
  78. ^ Garey & Johnson (1979): SP9
  79. ^ Garey & Johnson (1979): SP10
  80. ^ Garey & Johnson (1979): SP11
  81. ^ Garey & Johnson (1979): SR1
  82. ^ Garey & Johnson (1979): SR2
  83. ^ Garey & Johnson (1979): SR3
  84. ^ Garey & Johnson (1979): SR4
  85. ^ Garey & Johnson (1979): SR5
  86. ^ Garey & Johnson (1979): SR6
  87. ^ Garey & Johnson (1979): SR7
  88. ^ Garey & Johnson (1979): SR8
  89. ^ Garey & Johnson (1979): SR9
  90. ^ Garey & Johnson (1979): SR10
  91. ^ Garey & Johnson (1979): SR11
  92. ^ Garey & Johnson (1979): SR12
  93. ^ Garey & Johnson (1979): SR13
  94. ^ Garey & Johnson (1979): SR14
  95. ^ Garey & Johnson (1979): SR15
  96. ^ Garey & Johnson (1979): SR16
  97. ^ Garey & Johnson (1979): SR17
  98. ^ Garey & Johnson (1979): SR18
  99. ^ Garey & Johnson (1979): SR19
  100. ^ Garey & Johnson (1979): SR20
  101. ^ Garey & Johnson (1979): SR21
  102. ^ Garey & Johnson (1979): SR22
  103. ^ Garey & Johnson (1979): SR23
  104. ^ Garey & Johnson (1979): SR24
  105. ^ Garey & Johnson (1979): SR25
  106. ^ Garey & Johnson (1979): SR26
  107. ^ Garey & Johnson (1979): SR27
  108. ^ Garey & Johnson (1979): SR28
  109. ^ Garey & Johnson (1979): SR29
  110. ^ Garey & Johnson (1979): SR30
  111. ^ Garey & Johnson (1979): SR31
  112. ^ Garey & Johnson (1979): SR32
  113. ^ Garey & Johnson (1979): SR33
  114. ^ Garey & Johnson (1979): SR34
  115. ^ Garey & Johnson (1979): SR35
  116. ^ Garey & Johnson (1979): SR36
  117. ^ http://www.cs.rpi.edu/~civria/max-vol-inapprox.pdf
  118. ^ Yato, Takauki (2003). "Complexity and Completeness of Finding Another Solution and its Application to Puzzles". CiteSeerX: 10.1.1.103.8380. 
  119. ^ R. Clifford, M. Jalsenius, A. Montanaro and B. Sach (2010-08-19). The Complexity of Flood Filling Games. arXiv:1001.4420. 
  120. ^ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.
  121. ^ Holzer & Ruepp (2007)
  122. ^ Cormode, Graham (2004). "The hardness of the lemmings game, or Oh no, more NP-completeness proofs". http://dimacs.rutgers.edu/~graham/pubs/papers/cormodelemmings.pdf. 
  123. ^ Friedman, Erich (2012-03-27). "Pearl Puzzles are NP-complete". http://www2.stetson.edu/~efriedma/papers/pearl/pearl.html. 
  124. ^ Kaye (2000)
  125. ^ G. Aloupis, E. D. Demaine, A. Guo (2012-03-09). "Classic Nintendo Games are (NP-)Hard". http://arxiv.org/pdf/1203.1895v1.pdf. 
  126. ^ Garey & Johnson (1979): LO1
  127. ^ Garey & Johnson (1979): LO2
  128. ^ Garey & Johnson (1979): LO3
  129. ^ Garey & Johnson (1979): LO4
  130. ^ Garey & Johnson (1979): LO5
  131. ^ Garey & Johnson (1979): LO6
  132. ^ Garey & Johnson (1979): LO8
  133. ^ Garey & Johnson (1979): LO9
  134. ^ Garey & Johnson (1979): LO10
  135. ^ Garey & Johnson (1979): AL7
  136. ^ Garey & Johnson (1979): AL8
  137. ^ Garey & Johnson (1979): AL10
  138. ^ Garey & Johnson (1979): AL11
  139. ^ Garey & Johnson (1979): AL15
  140. ^ Garey & Johnson (1979): AL17
  141. ^ Garey & Johnson (1979): AL18
  142. ^ H. Breu and David G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3–24, 1998
  143. ^ "Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165.
  144. ^ Barry A. Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6.

  References

  • Cormode, Graham (2004). "The hardness of the lemmings game, or Oh no, more NP-completeness proofs". Proceedings of Third International Conference on Fun with Algorithms (FUN 2004). pp. 65-76. 
   
               

 

All translations of list of np-complete problems


sensagent's content

  • definitions
  • synonyms
  • antonyms
  • encyclopedia

Dictionary and translator for handheld

⇨ New : sensagent is now available on your handheld

   Advertising ▼

sensagent's office

Shortkey or widget. Free.

Windows Shortkey: sensagent. Free.

Vista Widget : sensagent. Free.

Webmaster Solution

Alexandria

A windows (pop-into) of information (full-content of Sensagent) triggered by double-clicking any word on your webpage. Give contextual explanation and translation from your sites !

Try here  or   get the code

SensagentBox

With a SensagentBox, visitors to your site can access reliable information on over 5 million pages provided by Sensagent.com. Choose the design that fits your site.

Business solution

Improve your site content

Add new content to your site from Sensagent by XML.

Crawl products or adds

Get XML access to reach the best products.

Index images and define metadata

Get XML access to fix the meaning of your metadata.


Please, email us to describe your idea.

WordGame

The English word games are:
○   Anagrams
○   Wildcard, crossword
○   Lettris
○   Boggle.

Lettris

Lettris is a curious tetris-clone game where all the bricks have the same square shape but different content. Each square carries a letter. To make squares disappear and save space for other squares you have to assemble English words (left, right, up, down) from the falling squares.

boggle

Boggle gives you 3 minutes to find as many words (3 letters or more) as you can in a grid of 16 letters. You can also try the grid of 16 letters. Letters must be adjacent and longer words score better. See if you can get into the grid Hall of Fame !

English dictionary
Main references

Most English definitions are provided by WordNet .
English thesaurus is mainly derived from The Integral Dictionary (TID).
English Encyclopedia is licensed by Wikipedia (GNU).

Copyrights

The wordgames anagrams, crossword, Lettris and Boggle are provided by Memodata.
The web service Alexandria is granted from Memodata for the Ebay search.
The SensagentBox are offered by sensAgent.

Translation

Change the target language to find translations.
Tips: browse the semantic fields (see From ideas to words) in two languages to learn more.

last searches on the dictionary :

3937 online visitors

computed in 0.047s

   Advertising ▼

I would like to report:
section :
a spelling or a grammatical mistake
an offensive content(racist, pornographic, injurious, etc.)
a copyright violation
an error
a missing statement
other
please precise:

Advertize

Partnership

Company informations

My account

login

registration

   Advertising ▼