38:
396:
If P and NP are different, then there exist decision problems in the region of NP that fall between P and the NP-complete problems. (If P and NP are the same class, then NP-intermediate problems do not exist because in this case every NP-complete problem would fall in P, and by definition, every
107:
in polynomial time. As a consequence, finding a polynomial time algorithm to solve a single NP-hard problem would give polynomial time algorithms for all the problems in the complexity class
364:
Class of problems which are at least as hard as the hardest problems in NP. Problems that are NP-hard do not have to be elements of NP; indeed, they may not even be decidable.
297:
assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem is not in
805:
199:
in polynomial time so this new definition implies the previous one. It does not restrict the class NP-hard to decision problems, and it also includes
250:). For example, the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph—commonly known as the
231:
227:
56:, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete)
285:
question and so is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete. For example, the
1167:
758:
721:
689:
586:
798:
334:
314:
61:
518:
286:
745:
247:
137:, and therefore even more difficult to solve than all problems in NP, but they are provably not NP-hard (unless P=NP).
1207:
791:
251:
990:
1183:
1202:
750:
471:
301:
since all problems in NP are decidable in a finite number of operations, but the halting problem, in general, is
81:
1172:
415:
372:
Class of decision problems which contains the hardest problems in NP. Each NP-complete problem has to be in NP.
430:
219:
1126:
476:
258:
is another example: given a set of integers, does any non-empty subset of them add up to zero? That is a
1121:
1116:
410:
234:). There are many classes of approximability, each one enabling approximation up to a different level.
333:
NP-hard problems do not have to be elements of the complexity class NP. As NP plays a central role in
1111:
204:
302:
134:
53:
31:
559:
350:-solution can be verified as a solution in polynomial time by a deterministic Turing machine (or
277:. That is the problem which asks "given a program and its input, will it run forever?" That is a
255:
157:
119:
1131:
772:
754:
717:
711:
685:
673:
582:
524:
514:
466:
52:, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that
1095:
985:
917:
907:
814:
740:
650:
Escoffier, B.; Paschos, B.Th. (2010). "A survey on the structure of approximation classes".
551:
259:
146:
1020:
768:
1090:
1080:
1037:
1027:
1010:
1000:
958:
953:
948:
932:
912:
890:
885:
880:
868:
863:
858:
853:
764:
705:
506:
391:
341:
274:
243:
130:
108:
77:
49:
37:
1085:
973:
895:
848:
290:
200:
45:
1196:
736:
678:
669:
481:
435:
383:
41:
563:
420:
171:
Another definition is to require that there be a polynomial-time reduction from an
406:
NP-hard problems are often tackled with rules-based languages in areas including:
289:
can be reduced to the halting problem by transforming it to the description of a
115:, it is unlikely that any polynomial-time algorithms for NP-hard problems exist.
873:
425:
367:
294:
172:
112:
388:
Decision problems that are both NP-hard and NP-easy, but not necessarily in NP.
1075:
900:
776:
528:
1070:
602:
555:
680:
The
Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization
626:
603:"Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP"
1065:
1060:
1005:
828:
749:. Series of Books in the Mathematical Sciences (1st ed.). New York:
454:
440:
215:
If P ≠ NP, then NP-hard problems could not be solved in polynomial time.
129:
is NP-hard, then it is at least as difficult to solve as the problems in
1055:
375:
17:
1015:
746:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
1162:
1157:
1032:
783:
322:
318:
1152:
1147:
968:
222:
up to some constant approximation ratio (in particular, those in
133:. However, the opposite direction is not true: some problems are
980:
838:
787:
713:
Complexity Theory: Exploring the Limits of
Efficient Algorithms
513:. Vol. A, Algorithms and complexity. Amsterdam: Elsevier.
995:
927:
922:
843:
833:
223:
346:
Class of computational decision problems for which any given
321:, but not in non-deterministic polynomial time (unless NP =
542:
Knuth, Donald (1974). "Postscript about NP-hard problems".
218:
Some NP-hard optimization problems can be polynomial-time
397:
problem in NP can be reduced to an NP-complete problem.)
627:"Is undecidable(complement of R) a subset of NP-hard?"
1140:
1104:
1048:
941:
821:
305:. There are also NP-hard problems that are neither
677:
226:) or even up to any approximation ratio (those in
577:Daniel Pierre Bovet; Pierluigi Crescenzi (1994).
380:At most as hard as NP, but not necessarily in NP.
676:; Rinnooy Kan, A. H. G.; Shmoys, D. B. (1985),
337:, it is used as the basis of several classes:
118:A simple example of an NP-hard problem is the
799:
8:
806:
792:
784:
501:
499:
497:
111:. As it is suspected, but unproven, that
579:Introduction to the Theory of Complexity
511:Handbook of Theoretical Computer Science
36:
493:
265:There are decision problems that are
7:
187:in NP reduces in polynomial time to
358:Turing machine in polynomial time).
92:. That is, assuming a solution for
158:polynomial-time many-one reduction
152:is NP-hard when for every problem
25:
1168:Probabilistically checkable proof
704:More precisely, this language is
78:non-deterministic polynomial-time
315:true quantified Boolean formulas
313:. For instance, the language of
103:s solution can be used to solve
30:For a gentler introduction, see
631:Computer Science Stack Exchange
262:and happens to be NP-complete.
246:problems are also NP-hard (see
62:computational complexity theory
445:Process monitoring and control
287:Boolean satisfiability problem
1:
581:. Prentice Hall. p. 69.
248:List of NP-complete problems
252:travelling salesman problem
1224:
1184:List of complexity classes
64:, a computational problem
29:
1181:
751:W. H. Freeman and Company
716:, Springer, p. 189,
684:, John Wiley & Sons,
472:List of unsolved problems
82:polynomial-time reduction
1173:Interactive proof system
335:computational complexity
652:Computer Science Review
556:10.1145/1008304.1008305
451:Routing/vehicle routing
254:—is NP-hard. The
76:which can be solved in
72:if, for every problem
1127:Arithmetical hierarchy
710:Wegener, Ingo (2005),
477:Reduction (complexity)
57:
1122:Grzegorczyk hierarchy
1117:Exponential hierarchy
1049:Considered infeasible
607:www.scottaaronson.com
411:Approximate computing
205:optimization problems
40:
1112:Polynomial hierarchy
942:Suspected infeasible
708:; see, for example,
448:Rosters or schedules
329:NP-naming convention
1141:Families of classes
822:Considered feasible
195:reduces in turn to
96:takes 1 unit time,
32:P versus NP problem
1208:Complexity classes
815:Complexity classes
256:subset sum problem
156:in NP, there is a
120:subset sum problem
58:
1190:
1189:
1132:Boolean hierarchy
1105:Class hierarchies
741:Johnson, David S.
737:Garey, Michael R.
467:Lists of problems
402:Application areas
356:non-deterministic
183:. As any problem
16:(Redirected from
1215:
1203:NP-hard problems
808:
801:
794:
785:
780:
728:
726:
702:
696:
694:
683:
666:
660:
659:
647:
641:
640:
638:
637:
623:
617:
616:
614:
613:
599:
593:
592:
574:
568:
567:
539:
533:
532:
507:Leeuwen, Jan van
503:
431:Decision support
319:polynomial space
317:is decidable in
260:decision problem
147:decision problem
102:
27:Complexity class
21:
1223:
1222:
1218:
1217:
1216:
1214:
1213:
1212:
1193:
1192:
1191:
1186:
1177:
1136:
1100:
1044:
1038:PSPACE-complete
937:
817:
812:
761:
735:
732:
731:
724:
709:
706:PSPACE-complete
703:
699:
692:
668:
667:
663:
649:
648:
644:
635:
633:
625:
624:
620:
611:
609:
601:
600:
596:
589:
576:
575:
571:
544:ACM SIGACT News
541:
540:
536:
521:
505:
504:
495:
490:
463:
404:
392:NP-intermediate
331:
293:that tries all
275:halting problem
240:
213:
201:search problems
143:
125:Informally, if
100:
35:
28:
23:
22:
15:
12:
11:
5:
1221:
1219:
1211:
1210:
1205:
1195:
1194:
1188:
1187:
1182:
1179:
1178:
1176:
1175:
1170:
1165:
1160:
1155:
1150:
1144:
1142:
1138:
1137:
1135:
1134:
1129:
1124:
1119:
1114:
1108:
1106:
1102:
1101:
1099:
1098:
1093:
1088:
1083:
1078:
1073:
1068:
1063:
1058:
1052:
1050:
1046:
1045:
1043:
1042:
1041:
1040:
1030:
1025:
1024:
1023:
1013:
1008:
1003:
998:
993:
988:
983:
978:
977:
976:
974:co-NP-complete
971:
966:
961:
951:
945:
943:
939:
938:
936:
935:
930:
925:
920:
915:
910:
905:
904:
903:
893:
888:
883:
878:
877:
876:
866:
861:
856:
851:
846:
841:
836:
831:
825:
823:
819:
818:
813:
811:
810:
803:
796:
788:
782:
781:
759:
730:
729:
722:
697:
690:
674:Lenstra, J. K.
661:
642:
618:
594:
587:
569:
534:
519:
509:, ed. (1998).
492:
491:
489:
486:
485:
484:
479:
474:
469:
462:
459:
458:
457:
452:
449:
446:
443:
438:
433:
428:
423:
418:
413:
403:
400:
399:
398:
394:
389:
386:
381:
378:
373:
370:
365:
362:
359:
344:
330:
327:
291:Turing machine
239:
236:
212:
209:
142:
139:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1220:
1209:
1206:
1204:
1201:
1200:
1198:
1185:
1180:
1174:
1171:
1169:
1166:
1164:
1161:
1159:
1156:
1154:
1151:
1149:
1146:
1145:
1143:
1139:
1133:
1130:
1128:
1125:
1123:
1120:
1118:
1115:
1113:
1110:
1109:
1107:
1103:
1097:
1094:
1092:
1089:
1087:
1084:
1082:
1079:
1077:
1074:
1072:
1069:
1067:
1064:
1062:
1059:
1057:
1054:
1053:
1051:
1047:
1039:
1036:
1035:
1034:
1031:
1029:
1026:
1022:
1019:
1018:
1017:
1014:
1012:
1009:
1007:
1004:
1002:
999:
997:
994:
992:
989:
987:
984:
982:
979:
975:
972:
970:
967:
965:
962:
960:
957:
956:
955:
952:
950:
947:
946:
944:
940:
934:
931:
929:
926:
924:
921:
919:
916:
914:
911:
909:
906:
902:
899:
898:
897:
894:
892:
889:
887:
884:
882:
879:
875:
872:
871:
870:
867:
865:
862:
860:
857:
855:
852:
850:
847:
845:
842:
840:
837:
835:
832:
830:
827:
826:
824:
820:
816:
809:
804:
802:
797:
795:
790:
789:
786:
778:
774:
770:
766:
762:
760:9780716710455
756:
752:
748:
747:
742:
738:
734:
733:
725:
723:9783540210450
719:
715:
714:
707:
701:
698:
693:
691:0-471-90413-9
687:
682:
681:
675:
671:
670:Lawler, E. L.
665:
662:
657:
653:
646:
643:
632:
628:
622:
619:
608:
604:
598:
595:
590:
588:0-13-915380-2
584:
580:
573:
570:
565:
561:
557:
553:
549:
545:
538:
535:
530:
526:
522:
516:
512:
508:
502:
500:
498:
494:
487:
483:
482:Unknowability
480:
478:
475:
473:
470:
468:
465:
464:
460:
456:
453:
450:
447:
444:
442:
439:
437:
436:Phylogenetics
434:
432:
429:
427:
424:
422:
419:
417:
416:Configuration
414:
412:
409:
408:
407:
401:
395:
393:
390:
387:
385:
384:NP-equivalent
382:
379:
377:
374:
371:
369:
366:
363:
360:
357:
353:
349:
345:
343:
340:
339:
338:
336:
328:
326:
324:
320:
316:
312:
308:
304:
300:
296:
292:
288:
284:
280:
276:
272:
268:
263:
261:
257:
253:
249:
245:
237:
235:
233:
229:
225:
221:
216:
210:
208:
206:
202:
198:
194:
190:
186:
182:
178:
174:
169:
167:
163:
159:
155:
151:
148:
140:
138:
136:
132:
128:
123:
121:
116:
114:
110:
106:
99:
95:
91:
87:
83:
80:, there is a
79:
75:
71:
67:
63:
55:
51:
47:
43:
42:Euler diagram
39:
33:
19:
963:
744:
712:
700:
679:
664:
655:
651:
645:
634:. Retrieved
630:
621:
610:. Retrieved
606:
597:
578:
572:
550:(2): 15–16.
547:
543:
537:
510:
421:Cryptography
405:
355:
351:
347:
332:
310:
306:
298:
282:
278:
273:such as the
270:
266:
264:
241:
220:approximated
217:
214:
211:Consequences
196:
192:
188:
184:
180:
176:
170:
165:
161:
153:
149:
144:
126:
124:
117:
104:
97:
93:
89:
85:
73:
69:
65:
59:
1021:#P-complete
959:NP-complete
874:NL-complete
658:(1): 19–40.
426:Data mining
368:NP-complete
311:Undecidable
307:NP-complete
303:undecidable
295:truth value
271:NP-complete
244:NP-complete
173:NP-complete
135:undecidable
1197:Categories
1076:ELEMENTARY
901:P-complete
636:2024-02-09
612:2016-09-25
520:0262720140
488:References
455:Scheduling
141:Definition
68:is called
1071:2-EXPTIME
777:247570676
529:247934368
1066:EXPSPACE
1061:NEXPTIME
829:DLOGTIME
743:(1979).
564:46480926
461:See also
441:Planning
352:solvable
269:but not
238:Examples
175:problem
1056:EXPTIME
964:NP-hard
769:0519066
376:NP-easy
361:NP-hard
267:NP-hard
70:NP-hard
18:NP-Hard
1163:NSPACE
1158:DSPACE
1033:PSPACE
775:
767:
757:
720:
688:
585:
562:
527:
517:
323:PSPACE
1153:NTIME
1148:DTIME
969:co-NP
560:S2CID
354:by a
232:FPTAS
160:from
101:'
84:from
981:TFNP
773:OCLC
755:ISBN
718:ISBN
686:ISBN
583:ISBN
525:OCLC
515:ISBN
309:nor
242:All
228:PTAS
113:P≠NP
54:P≠NP
44:for
1096:ALL
996:QMA
986:FNP
928:APX
923:BQP
918:BPP
908:ZPP
839:ACC
552:doi
348:yes
325:).
279:yes
230:or
224:APX
203:or
179:to
164:to
88:to
60:In
1199::
1091:RE
1081:PR
1028:IP
1016:#P
1011:PP
1006:⊕P
1001:PH
991:AM
954:NP
949:UP
933:FP
913:RP
891:CC
886:SC
881:NC
869:NL
864:FL
859:RL
854:SL
844:TC
834:AC
771:.
765:MR
763:.
753:.
739:;
672:;
654:.
629:.
605:.
558:.
546:.
523:.
496:^
342:NP
299:NP
283:no
207:.
191:,
168:.
145:A
131:NP
122:.
109:NP
50:NP
48:,
1086:R
896:P
849:L
807:e
800:t
793:v
779:.
727:.
695:.
656:4
639:.
615:.
591:.
566:.
554::
548:6
531:.
281:/
197:H
193:L
189:G
185:L
181:H
177:G
166:H
162:L
154:L
150:H
127:H
105:L
98:H
94:H
90:H
86:L
74:L
66:H
46:P
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
