﻿ list of np-complete problems : definition of list of np-complete problems and synonyms of list of np-complete problems (English)
 »
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

# 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.

## 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).

## Network design

### 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.

## 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

## 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].

## 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.

## Notes

1. ^ Garey & Johnson (1979): GT1
2. ^ Garey & Johnson (1979): GT2
3. ^ Garey & Johnson (1979): GT3
4. ^ Garey & Johnson (1979): GT4
5. ^ Garey & Johnson (1979): GT15
6. ^ Garey & Johnson (1979): GT5
7. ^ Garey & Johnson (1979): GT6
8. ^ Garey & Johnson (1979): GT7
9. ^ Garey & Johnson (1979): GT8
10. ^ Garey & Johnson (1979): GT9
11. ^ Minimum Independent Dominating Set
12. ^ Garey & Johnson (1979): GT10
13. ^ Garey & Johnson (1979): GT11
14. ^ Garey & Johnson (1979): GT12
15. ^ Garey & Johnson (1979): GT13
16. ^ Garey & Johnson (1979): GT14
17. ^ Garey & Johnson (1979): GT16
18. ^ Garey & Johnson (1979): GT17
19. ^ Garey & Johnson (1979): GT18
20. ^ a b Garey & Johnson (1979): GT56
21. ^ a b
22. ^ Garey & Johnson (1979): GT19
23. ^ Garey & Johnson (1979): GT20
24. ^ Garey & Johnson (1979): GT23
25. ^ Garey & Johnson (1979): GT24
26. ^ Garey & Johnson (1979): GT25
27. ^ Garey & Johnson (1979): GT26
28. ^ Garey & Johnson (1979): GT27
29. ^ Garey & Johnson (1979): GT28
30. ^ Garey & Johnson (1979): GT29
31. ^ Garey & Johnson (1979): GT30
32. ^ Garey & Johnson (1979): GT31
33. ^ Garey & Johnson (1979): GT32
34. ^ Garey & Johnson (1979): GT33
35. ^ Garey & Johnson (1979): GT34
36. ^ Garey & Johnson (1979): GT35
37. ^ Garey & Johnson (1979): GT36
38. ^ Garey & Johnson (1979): GT37
39. ^ Garey & Johnson (1979): GT38
40. ^ Garey & Johnson (1979): GT39
41. ^ Garey & Johnson (1979): GT40
42. ^ Garey & Johnson (1979): GT41
43. ^ Garey & Johnson (1979): GT42
44. ^ Garey & Johnson (1979): GT43
45. ^ Garey & Johnson (1979): GT44
46. ^ Garey & Johnson (1979): GT45
47. ^ Garey & Johnson (1979): GT46
48. ^ Garey & Johnson (1979): GT47
49. ^
50. ^ Garey & Johnson (1979): GT48
51. ^ Garey & Johnson (1979): GT49
52. ^ Garey & Johnson (1979): GT50
53. ^ Garey & Johnson (1979): GT51
54. ^ Garey & Johnson (1979): GT52
55. ^ Garey & Johnson (1979): GT53
56. ^ Garey & Johnson (1979): GT54
57. ^ Garey & Johnson (1979): GT55
58. ^ Garey & Johnson (1979): GT57
59. ^ Garey & Johnson (1979): GT58
60. ^ Garey & Johnson (1979): GT59
61. ^ Garey & Johnson (1979): GT60
62. ^ Garey & Johnson (1979): GT61
63. ^ Garey & Johnson (1979): GT62
64. ^ Garey & Johnson (1979): GT63
65. ^ Garey & Johnson (1979): GT64
66. ^ Garey & Johnson (1979): GT65
67. ^
68. ^ 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.
69. ^ Garey & Johnson (1979): SP1
70. ^ Garey & Johnson (1979): SP2
71. ^ Garey & Johnson (1979): SP3
72. ^ Garey & Johnson (1979): SP4
73. ^ Garey & Johnson (1979): SP5
74. ^ Garey & Johnson (1979): SP6
75. ^ Garey & Johnson (1979): SP7
76. ^ Garey & Johnson (1979): SP8
77. ^ Garey & Johnson (1979): SP9
78. ^ Garey & Johnson (1979): SP10
79. ^ Garey & Johnson (1979): SP11
80. ^ Garey & Johnson (1979): SR1
81. ^ Garey & Johnson (1979): SR2
82. ^ Garey & Johnson (1979): SR3
83. ^ Garey & Johnson (1979): SR4
84. ^ Garey & Johnson (1979): SR5
85. ^ Garey & Johnson (1979): SR6
86. ^ Garey & Johnson (1979): SR7
87. ^ Garey & Johnson (1979): SR8
88. ^ Garey & Johnson (1979): SR9
89. ^ Garey & Johnson (1979): SR10
90. ^ Garey & Johnson (1979): SR11
91. ^ Garey & Johnson (1979): SR12
92. ^ Garey & Johnson (1979): SR13
93. ^ Garey & Johnson (1979): SR14
94. ^ Garey & Johnson (1979): SR15
95. ^ Garey & Johnson (1979): SR16
96. ^ Garey & Johnson (1979): SR17
97. ^ Garey & Johnson (1979): SR18
98. ^ Garey & Johnson (1979): SR19
99. ^ Garey & Johnson (1979): SR20
100. ^ Garey & Johnson (1979): SR21
101. ^ Garey & Johnson (1979): SR22
102. ^ Garey & Johnson (1979): SR23
103. ^ Garey & Johnson (1979): SR24
104. ^ Garey & Johnson (1979): SR25
105. ^ Garey & Johnson (1979): SR26
106. ^ Garey & Johnson (1979): SR27
107. ^ Garey & Johnson (1979): SR28
108. ^ Garey & Johnson (1979): SR29
109. ^ Garey & Johnson (1979): SR30
110. ^ Garey & Johnson (1979): SR31
111. ^ Garey & Johnson (1979): SR32
112. ^ Garey & Johnson (1979): SR33
113. ^ Garey & Johnson (1979): SR34
114. ^ Garey & Johnson (1979): SR35
115. ^ Garey & Johnson (1979): SR36
116. ^ http://www.cs.rpi.edu/~civria/max-vol-inapprox.pdf
117. ^ Yato, Takauki (2003). "Complexity and Completeness of Finding Another Solution and its Application to Puzzles". CiteSeerX: 10.1.1.103.8380.
118. ^ R. Clifford, M. Jalsenius, A. Montanaro and B. Sach (2010-08-19). The Complexity of Flood Filling Games. arXiv:1001.4420.
119. ^ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.
120. ^
121. ^
122. ^ Friedman, Erich (2012-03-27). "Pearl Puzzles are NP-complete".
123. ^
124. ^ G. Aloupis, E. D. Demaine, A. Guo (2012-03-09). "Classic Nintendo Games are (NP-)Hard".
125. ^ Garey & Johnson (1979): LO1
126. ^ Garey & Johnson (1979): LO2
127. ^ Garey & Johnson (1979): LO3
128. ^ Garey & Johnson (1979): LO4
129. ^ Garey & Johnson (1979): LO5
130. ^ Garey & Johnson (1979): LO6
131. ^ Garey & Johnson (1979): LO8
132. ^ Garey & Johnson (1979): LO9
133. ^ Garey & Johnson (1979): LO10
134. ^ Garey & Johnson (1979): AL7
135. ^ Garey & Johnson (1979): AL8
136. ^ Garey & Johnson (1979): AL10
137. ^ Garey & Johnson (1979): AL11
138. ^ Garey & Johnson (1979): AL15
139. ^ Garey & Johnson (1979): AL17
140. ^ Garey & Johnson (1979): AL18
141. ^ H. Breu and David G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3–24, 1998
142. ^ "Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165.
143. ^ 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.

sensagent's content

• definitions
• synonyms
• antonyms
• encyclopedia

Dictionary and translator for handheld

New : sensagent is now available on your handheld

sensagent's office

Shortkey or widget. Free.

Windows Shortkey: . Free.

Vista Widget : . 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.

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).

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 :

3685 online visitors

computed in 0.047s

I would like to report:
section :
a spelling or a grammatical mistake
an offensive content(racist, pornographic, injurious, etc.)