90:. The most frequently used of these are the many-one reductions, and in some cases the phrase "polynomial-time reduction" may be used to mean a polynomial-time many-one reduction. The most general reductions are the Turing reductions and the most restrictive are the many-one reductions with truth-table reductions occupying the space in between.
491:(the class of polynomial-time decision problems) may be reduced to every other nontrivial decision problem (where nontrivial means that not every input has the same output), by a polynomial-time many-one reduction. To transform an instance of problem
46:
it to inputs for the second problem and calling the subroutine one or more times. If both the time required to transform the first problem to the second, and the number of times the subroutine is called is
574:
do not involve reductions: reductions come into their study only in the definition of complete languages for these classes. However, in some cases a complexity class may be defined by reductions. If
782:
753:
720:
666:
62:, if no efficient algorithm exists for the first problem, none exists for the second either. Polynomial-time reductions are frequently used in complexity theory for defining both
312:
626:
390:
194:
722:
is the set of problems having a polynomial-time many-one reduction to the existential theory of the reals; it has several other complete problems such as determining the
227:
1104:. In particular, for the argument that every nontrivial problem in P has a polynomial-time many-one reduction to every other nontrivial problem, see p. 48.
17:
392:. Many-one reductions can be regarded as restricted variants of Turing reductions where the number of calls made to the subroutine for problem
465:-complete problem. Polynomial-time many-one reductions have been used to define complete problems for other complexity classes, including the
533:
itself, polynomial-time reductions cannot be used to define complete languages: if they were used in this way, every nontrivial problem in
1122:
54:
A polynomial-time reduction proves that the first problem is no more difficult than the second one, because whenever an efficient
1171:
1142:
1098:
1073:
1012:
936:
881:
78:
The three most common types of polynomial-time reduction, from the most to the least restrictive, are polynomial-time
967:
909:
828:
1201:
669:
31:
396:
is exactly one and the value returned by the reduction is the same value as the one returned by the subroutine.
723:
346:, and polynomial time outside of those subroutine calls. Polynomial-time Turing reductions are also known as
762:
733:
700:
646:
931:. 34th International Conference on Foundation of Software Technology and Theoretical Computer Science.
1124:
Graph
Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers
276:
798:
593:
357:
161:
995:
257:, such that the output for the original problem can be expressed as a function of the outputs for
199:
928:
Separating Cook
Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis
990:
43:
985:; Hay, L. (1988), "On truth-table reducibility to SAT and the difference hierarchy over NP",
547:
reductions are used for defining classes of complete problems for these classes, such as the
238:
122:, such that the transformed problem has the same output as the original problem. An instance
83:
694:
249:(both decision problems) is a polynomial time algorithm for transforming inputs to problem
42:
solving the second problem exists, then the first problem can be solved by transforming or
8:
538:
1127:, Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, pp. 334–344,
503:
in polynomial time, and then use the solution to choose one of two instances of problem
99:
79:
1177:
1167:
1138:
1094:
1069:
1008:
963:
932:
926:
905:
877:
146:, and returning its output. Polynomial-time many-one reductions may also be known as
815:-complete if it is complete for this class; the graph isomorphism problem itself is
461:-complete by finding a single polynomial-time many-one reduction to it from a known
38:
is a method for solving one problem using another. One shows that if a hypothetical
1128:
1059:
1032:
1000:
727:
579:
405:
323:
111:
87:
67:
63:
1133:
1115:
1064:
806:
792:
542:
524:
518:
472:
466:
444:
1159:
955:
512:
486:
59:
840:
1195:
1181:
1028:
865:
869:
58:
exists for the second problem, one exists for the first problem as well. By
897:
351:
155:
1004:
453:
have polynomial-time many-one reductions to it. A problem that belongs to
982:
437:
270:
1051:
548:
48:
39:
1037:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
841:
MIT OpenCourseWare: 16. Complexity: P, NP, NP-completeness, Reductions
987:
Proceedings of Third Annual
Structure in Complexity Theory Conference
335:
130:
can be solved by applying this transformation to produce an instance
55:
51:, then the first problem is polynomial-time reducible to the second.
114:) is a polynomial-time algorithm for transforming inputs to problem
269:
must be the same for all inputs, so that it can be expressed by a
811:, the same is true for every problem in this class. A problem is
673:
507:
with different answers. Therefore, for complexity classes within
476:
1054:(2011), "Complexity theory", in Blum, E. K.; Aho, A. V. (eds.),
902:
Complexity Theory: Exploring the Limits of
Efficient Algorithms
681:
342:
using a polynomial number of calls to a subroutine for problem
354:. A reduction of this type may be denoted by the expression
273:. A reduction of this type may be denoted by the expression
925:
Mandal, Debasis; Pavan, A.; Venugopalan, Rajeswari (2014).
1164:
The Graph
Isomorphism Problem: Its Structural Complexity
1089:
Greenlaw, Raymond; Hoover, James; Ruzzo, Walter (1995),
1056:
Computer
Science: The Hardware, Software and Heart of It
1116:"Complexity of some geometric and topological problems"
924:
537:
would be complete. Instead, weaker reductions such as
1091:
Limits To
Parallel computation; P-Completeness Theory
801:. Since graph isomorphism is known to belong both to
765:
736:
703:
649:
596:
360:
279:
202:
164:
797:
consists of the problems that can be reduced to the
1157:
1088:
960:Computational Complexity: A Conceptual Perspective
860:
858:
856:
819:-complete, as are several other related problems.
776:
747:
714:
660:
620:
384:
306:
221:
188:
1193:
864:
853:
962:, Cambridge University Press, pp. 59–60,
672:, a computational problem that is known to be
557:
1027:
27:Method for solving one problem using another
950:
948:
643:An example of this is the complexity class
640:may have other complete problems as well.
562:The definitions of the complexity classes
110:(both of which are usually required to be
1132:
1063:
994:
954:
918:
770:
741:
708:
654:
582:, then one can define a complexity class
253:into a fixed number of inputs to problem
232:
158:. A reduction of this type is denoted by
142:as the input to an algorithm for problem
1113:
945:
981:
896:
876:. Pearson Education. pp. 452–453.
14:
1194:
755:inherits the property of belonging to
685:, but is not known to be complete for
93:
73:
261:. The function that maps outputs for
777:{\displaystyle \exists \mathbb {R} }
748:{\displaystyle \exists \mathbb {R} }
715:{\displaystyle \exists \mathbb {R} }
661:{\displaystyle \exists \mathbb {R} }
317:
1050:
632:will automatically be complete for
24:
766:
737:
704:
650:
25:
18:Polynomial-time many-one reduction
1213:
834:
1079:. See in particular p. 255.
791:Similarly, the complexity class
307:{\displaystyle A\leq _{tt}^{P}B}
1151:
670:existential theory of the reals
621:{\displaystyle A\leq _{m}^{P}C}
399:
385:{\displaystyle A\leq _{T}^{P}B}
189:{\displaystyle A\leq _{m}^{P}B}
32:computational complexity theory
1107:
1082:
1044:
1021:
975:
890:
829:Karp's 21 NP-complete problems
13:
1:
846:
436:. For instance, a problem is
412:and reduction ≤ is a problem
408:for a given complexity class
1134:10.1007/978-3-642-11805-0_32
1065:10.1007/978-1-4614-1168-0_12
586:consisting of the languages
7:
822:
724:rectilinear crossing number
558:Defining complexity classes
222:{\displaystyle A\leq _{p}B}
10:
1218:
485:Every decision problem in
420:, such that every problem
148:polynomial transformations
1114:Schaefer, Marcus (2010),
799:graph isomorphism problem
693:, or any language in the
36:polynomial-time reduction
1162:; Torán, Jacobo (1993),
904:, Springer, p. 60,
118:into inputs to problem
1202:Reduction (complexity)
778:
749:
716:
662:
622:
386:
308:
233:Truth-table reductions
223:
190:
84:truth-table reductions
1005:10.1109/SCT.1988.5282
784:-complete problem is
779:
750:
717:
663:
623:
387:
309:
239:truth-table reduction
224:
191:
1058:, pp. 241–267,
989:, pp. 224–233,
763:
734:
701:
695:polynomial hierarchy
647:
594:
539:log-space reductions
457:can be proven to be
449:and all problems in
358:
338:that solves problem
277:
265:into the output for
200:
162:
614:
378:
300:
182:
94:Many-one reductions
80:many-one reductions
74:Types of reductions
70:for those classes.
1158:Köbler, Johannes;
774:
745:
730:. Each problem in
712:
658:
618:
600:
382:
364:
322:A polynomial-time
304:
283:
237:A polynomial-time
219:
186:
168:
100:many-one reduction
98:A polynomial-time
64:complexity classes
1173:978-0-8176-3680-7
1144:978-3-642-11804-3
1100:978-0-19-508591-4
1075:978-1-4614-1167-3
1029:Garey, Michael R.
1014:978-0-8186-0866-7
938:978-3-939897-77-4
883:978-0-321-37291-8
668:defined from the
443:if it belongs to
318:Turing reductions
112:decision problems
88:Turing reductions
68:complete problems
16:(Redirected from
1209:
1186:
1184:
1155:
1149:
1147:
1136:
1120:
1111:
1105:
1103:
1086:
1080:
1078:
1067:
1048:
1042:
1040:
1025:
1019:
1017:
998:
979:
973:
972:
952:
943:
942:
922:
916:
914:
894:
888:
887:
874:Algorithm Design
862:
783:
781:
780:
775:
773:
754:
752:
751:
746:
744:
728:undirected graph
721:
719:
718:
713:
711:
667:
665:
664:
659:
657:
628:. In this case,
627:
625:
624:
619:
613:
608:
580:decision problem
428:has a reduction
416:that belongs to
406:complete problem
391:
389:
388:
383:
377:
372:
324:Turing reduction
313:
311:
310:
305:
299:
294:
228:
226:
225:
220:
215:
214:
195:
193:
192:
187:
181:
176:
21:
1217:
1216:
1212:
1211:
1210:
1208:
1207:
1206:
1192:
1191:
1190:
1189:
1174:
1156:
1152:
1145:
1118:
1112:
1108:
1101:
1087:
1083:
1076:
1049:
1045:
1039:, W. H. Freeman
1026:
1022:
1015:
980:
976:
970:
956:Goldreich, Oded
953:
946:
939:
923:
919:
912:
895:
891:
884:
863:
854:
849:
837:
825:
769:
764:
761:
760:
740:
735:
732:
731:
707:
702:
699:
698:
653:
648:
645:
644:
609:
604:
595:
592:
591:
560:
402:
373:
368:
359:
356:
355:
348:Cook reductions
326:from a problem
320:
295:
287:
278:
275:
274:
241:from a problem
235:
210:
206:
201:
198:
197:
177:
172:
163:
160:
159:
152:Karp reductions
102:from a problem
96:
76:
28:
23:
22:
15:
12:
11:
5:
1215:
1205:
1204:
1188:
1187:
1172:
1166:, Birkhäuser,
1150:
1143:
1106:
1099:
1081:
1074:
1043:
1033:Johnson, D. S.
1020:
1013:
974:
968:
944:
937:
917:
910:
889:
882:
866:Kleinberg, Jon
851:
850:
848:
845:
844:
843:
836:
835:External links
833:
832:
831:
824:
821:
772:
768:
743:
739:
710:
706:
656:
652:
617:
612:
607:
603:
599:
559:
556:
401:
398:
381:
376:
371:
367:
363:
350:, named after
319:
316:
303:
298:
293:
290:
286:
282:
234:
231:
218:
213:
209:
205:
185:
180:
175:
171:
167:
154:, named after
95:
92:
75:
72:
60:contraposition
26:
9:
6:
4:
3:
2:
1214:
1203:
1200:
1199:
1197:
1183:
1179:
1175:
1169:
1165:
1161:
1160:Schöning, Uwe
1154:
1146:
1140:
1135:
1130:
1126:
1125:
1117:
1110:
1102:
1096:
1092:
1085:
1077:
1071:
1066:
1061:
1057:
1053:
1047:
1038:
1034:
1030:
1024:
1016:
1010:
1006:
1002:
997:
996:10.1.1.5.2387
992:
988:
984:
978:
971:
969:9781139472746
965:
961:
957:
951:
949:
940:
934:
930:
929:
921:
913:
911:9783540274773
907:
903:
899:
898:Wegener, Ingo
893:
885:
879:
875:
871:
867:
861:
859:
857:
852:
842:
839:
838:
830:
827:
826:
820:
818:
814:
810:
809:
804:
800:
796:
795:
789:
787:
758:
729:
725:
696:
692:
688:
684:
683:
678:
676:
671:
641:
639:
635:
631:
615:
610:
605:
601:
597:
589:
585:
581:
577:
573:
569:
565:
555:
553:
551:
546:
545:
540:
536:
532:
528:
527:
522:
521:
516:
515:
510:
506:
502:
498:
494:
490:
489:
483:
481:
479:
474:
471:
469:
464:
460:
456:
452:
448:
447:
442:
440:
435:
431:
427:
423:
419:
415:
411:
407:
397:
395:
379:
374:
369:
365:
361:
353:
349:
345:
341:
337:
333:
330:to a problem
329:
325:
315:
301:
296:
291:
288:
284:
280:
272:
268:
264:
260:
256:
252:
248:
245:to a problem
244:
240:
230:
216:
211:
207:
203:
183:
178:
173:
169:
165:
157:
153:
149:
145:
141:
137:
133:
129:
125:
121:
117:
113:
109:
106:to a problem
105:
101:
91:
89:
85:
81:
71:
69:
65:
61:
57:
52:
50:
45:
41:
37:
33:
19:
1163:
1153:
1123:
1109:
1090:
1084:
1055:
1046:
1036:
1023:
986:
977:
959:
927:
920:
901:
892:
873:
816:
812:
807:
802:
793:
790:
785:
756:
690:
686:
680:
674:
642:
637:
633:
629:
587:
583:
575:
571:
567:
563:
561:
549:
543:
534:
530:
525:
519:
513:
508:
504:
500:
496:
492:
487:
484:
477:
467:
462:
458:
454:
450:
445:
438:
433:
429:
425:
421:
417:
413:
409:
403:
400:Completeness
393:
352:Stephen Cook
347:
343:
339:
331:
327:
321:
266:
262:
258:
254:
250:
246:
242:
236:
156:Richard Karp
151:
147:
143:
139:
135:
131:
127:
123:
119:
115:
107:
103:
97:
77:
53:
35:
29:
870:Tardos, Éva
759:, and each
482:languages.
271:truth table
134:of problem
126:of problem
1052:Aho, A. V.
983:Buss, S.R.
847:References
590:for which
554:problems.
49:polynomial
40:subroutine
1182:246882287
991:CiteSeerX
767:∃
738:∃
705:∃
651:∃
602:≤
552:-complete
480:-complete
473:languages
470:-complete
441:-complete
366:≤
336:algorithm
285:≤
208:≤
170:≤
138:, giving
56:algorithm
1196:Category
1035:(1979),
958:(2008),
900:(2005),
872:(2006).
823:See also
511:such as
499:, solve
44:reducing
805:and co-
788:-hard.
679:and in
578:is any
572:EXPTIME
478:EXPTIME
1180:
1170:
1141:
1097:
1072:
1011:
993:
966:
935:
908:
880:
757:PSPACE
726:of an
691:PSPACE
682:PSPACE
636:, but
570:, and
568:PSPACE
529:, and
468:PSPACE
334:is an
86:, and
1119:(PDF)
677:-hard
1178:OCLC
1168:ISBN
1139:ISBN
1095:ISBN
1070:ISBN
1009:ISBN
964:ISBN
933:ISBN
906:ISBN
878:ISBN
475:and
66:and
34:, a
1129:doi
1060:doi
1001:doi
541:or
495:to
424:in
196:or
150:or
30:In
1198::
1176:,
1137:,
1121:,
1093:,
1068:,
1031:;
1007:,
999:,
947:^
868:;
855:^
817:GI
813:GI
808:AM
803:NP
794:GI
786:NP
697:.
689:,
687:NP
675:NP
566:,
564:NP
544:NC
526:NC
523:,
520:NL
517:,
463:NP
459:NP
455:NP
451:NP
446:NP
439:NP
432:≤
404:A
314:.
229:.
82:,
1185:.
1148:.
1131::
1062::
1041:.
1018:.
1003::
941:.
915:.
886:.
771:R
742:R
709:R
655:R
638:C
634:C
630:C
616:C
611:P
606:m
598:A
588:A
584:C
576:C
550:P
535:P
531:P
514:L
509:P
505:B
501:A
497:B
493:A
488:P
434:P
430:A
426:C
422:A
418:C
414:P
410:C
394:B
380:B
375:P
370:T
362:A
344:B
340:A
332:B
328:A
302:B
297:P
292:t
289:t
281:A
267:A
263:B
259:B
255:B
251:A
247:B
243:A
217:B
212:p
204:A
184:B
179:P
174:m
166:A
144:B
140:y
136:B
132:y
128:A
124:x
120:B
116:A
108:B
104:A
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.