313:
showed in 1996 that every one of these 21 problems has a constrained optimization version that is impossible to approximate within any constant factor unless P = NP, by showing that Karp's approach to reduction generalizes to a specific type of approximability reduction. Note however that these may
309:
As time went on it was discovered that many of the problems can be solved efficiently if restricted to special cases, or can be solved within any fixed percentage of the optimal result. However,
66:
computational problems, thereby showing that they are all NP-complete. This was one of the first demonstrations that many natural computational problems occurring throughout
314:
be different from the standard optimization versions of the problems, which may have approximation algorithms (as in the case of maximum cut).
86:
Karp's 21 problems are shown below, many with their original names. The nesting indicates the direction of the reductions used. For example,
204:
484:
452:
503:
407:
310:
20:
107:
44:
498:
387:
323:
71:
119:
186:
174:
132:
112:
252:
28:
429:
245:
146:
8:
271:
160:
75:
413:
55:
48:
448:
403:
278:
153:
123:(A variation in which only the restrictions must be satisfied, with no optimization)
475:
440:
417:
395:
259:
167:
88:
67:
425:
52:
444:
217:
212:
127:
479:
492:
59:
383:
224:
63:
40:
36:
463:
399:
285:
238:
231:
139:
94:
32:
264:
35:. In his 1972 paper, "Reducibility Among Combinatorial Problems",
74:, and it drove interest in the study of NP-completeness and the
392:
Proc. 3rd Annual ACM Symposium on Theory of
Computing (STOC)
16:
Set of computational problems stated by
Richard Karp (1973)
435:. In R. E. Miller; J. W. Thatcher; J.D. Bohlinger (eds.).
58:
from the boolean satisfiability problem to each of 21
111:: the boolean satisfiability problem for formulas in
464:"On Unapproximable Versions of NP-Complete Problems"
360:
205:Satisfiability with at most 3 literals per clause
490:
348:
336:
388:"The Complexity of Theorem Proving Procedures"
263:(Karp's definition of Knapsack is closer to
430:"Reducibility Among Combinatorial Problems"
461:
366:
92:was shown to be NP-complete by reducing
491:
439:. New York: Plenum. pp. 85–103.
424:
382:
354:
342:
437:Complexity of Computer Computations
13:
14:
515:
304:
190:(Karp's name, now usually called
178:(Karp's name, now usually called
47:is NP-complete (also called the
81:
21:computational complexity theory
45:boolean satisfiability problem
25:Karp's 21 NP-complete problems
1:
376:
324:List of NP-complete problems
192:Undirected Hamiltonian cycle
7:
445:10.1007/978-1-4684-2001-2_9
317:
187:Undirected Hamilton circuit
115:(often referred to as SAT)
72:computationally intractable
10:
520:
180:Directed Hamiltonian cycle
51:) to show that there is a
504:Mathematics-related lists
480:10.1137/S0097539794266407
468:SIAM Journal on Computing
462:Zuckerman, David (1996).
175:Directed Hamilton circuit
43:'s 1971 theorem that the
329:
133:independent set problem
120:0–1 integer programming
113:conjunctive normal form
253:3-dimensional matching
218:Graph Coloring Problem
208:(equivalent to 3-SAT)
29:computational problems
400:10.1145/800157.805047
499:NP-complete problems
394:. pp. 151–158.
76:P versus NP problem
56:many-one reduction
49:Cook-Levin theorem
454:978-1-4684-2003-6
216:(also called the
161:Feedback node set
64:graph theoretical
511:
483:
474:(6): 1293–1304.
458:
434:
426:Karp, Richard M.
421:
370:
364:
358:
352:
346:
340:
213:Chromatic number
168:Feedback arc set
68:computer science
519:
518:
514:
513:
512:
510:
509:
508:
489:
488:
455:
432:
410:
379:
374:
373:
365:
361:
353:
349:
341:
337:
332:
320:
311:David Zuckerman
307:
84:
53:polynomial time
17:
12:
11:
5:
517:
507:
506:
501:
487:
486:
459:
453:
422:
408:
378:
375:
372:
371:
367:Zuckerman 1996
359:
347:
334:
333:
331:
328:
327:
326:
319:
316:
306:
305:Approximations
303:
302:
301:
300:
299:
298:
297:
296:
295:
294:
293:
292:
291:
290:
289:
275:
272:Job sequencing
256:
249:
242:
228:
201:
200:
199:
198:
197:
196:
195:
171:
164:
157:
143:
124:
108:Satisfiability
83:
80:
15:
9:
6:
4:
3:
2:
516:
505:
502:
500:
497:
496:
494:
485:
481:
477:
473:
469:
465:
460:
456:
450:
446:
442:
438:
431:
427:
423:
419:
415:
411:
409:9781450374644
405:
401:
397:
393:
389:
385:
384:Cook, Stephen
381:
380:
368:
363:
356:
351:
344:
339:
335:
325:
322:
321:
315:
312:
288:
287:
283:
282:
281:
280:
276:
274:
273:
269:
268:
266:
262:
261:
257:
255:
254:
250:
248:
247:
243:
241:
240:
236:
235:
234:
233:
229:
227:
226:
222:
221:
219:
215:
214:
210:
209:
207:
206:
202:
193:
189:
188:
184:
183:
181:
177:
176:
172:
170:
169:
165:
163:
162:
158:
156:
155:
151:
150:
149:
148:
144:
142:
141:
137:
136:
134:
130:
129:
125:
122:
121:
117:
116:
114:
110:
109:
105:
104:
103:
101:
97:
96:
91:
90:
79:
77:
73:
69:
65:
61:
60:combinatorial
57:
54:
50:
46:
42:
38:
34:
30:
27:are a set of
26:
22:
471:
467:
436:
391:
362:
350:
338:
308:
284:
277:
270:
258:
251:
246:Steiner tree
244:
237:
230:
225:Clique cover
223:
211:
203:
191:
185:
179:
173:
166:
159:
154:Set covering
152:
147:Vertex cover
145:
138:
126:
118:
106:
99:
93:
87:
85:
82:The problems
41:Stephen Cook
37:Richard Karp
24:
18:
239:Hitting set
232:Exact cover
140:Set packing
95:Exact cover
33:NP-complete
493:Categories
377:References
265:Subset sum
131:(see also
31:which are
355:Cook 1971
343:Karp 1972
279:Partition
428:(1972).
386:(1971).
318:See also
260:Knapsack
100:Knapsack
89:Knapsack
418:7573663
286:Max cut
451:
416:
406:
128:Clique
433:(PDF)
414:S2CID
330:Notes
39:used
449:ISBN
404:ISBN
70:are
62:and
476:doi
441:doi
396:doi
98:to
19:In
495::
472:25
470:.
466:.
447:.
412:.
402:.
390:.
267:)
220:)
182:)
135:)
102:.
78:.
23:,
482:.
478::
457:.
443::
420:.
398::
369:.
357:.
345:.
194:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.