198:
721:
237:
is one where the reduction uses the oracle answers as a basis for further computation, which may depend on the given answers but may not ask further questions of the oracle. It is so named because it weakens the constraints placed on a truth-table reduction, and provides a weaker equivalence
238:
classification; as such, a "weak truth-table reduction" can actually be more powerful than a truth-table reduction as a "tool", and perform a reduction that is not performable by truth table. Equivalently, a weak truth-table reduction is a Turing reduction for which the
415:
176:
during the computation; it may adaptively determine which questions it asks based upon answers to previous questions. In contrast, a truth-table reduction or a weak truth-table reduction must present all of its (finitely many)
160:, and strictly weaker. (That is, not every Turing reduction between sets can be performed by a truth-table reduction, but every truth-table reduction can be performed by a Turing reduction.) A Turing reduction from a set
421:
or in other words, one-one reducibility implies many-one reducibility, which implies truth-table reducibility, which in turn implies weak truth-table reducibility, which in turn implies Turing reducibility.
302:
655:
557:
615:
466:
675:
585:
518:
486:
151:
123:
103:
83:
63:
762:
786:
706:
698:
781:
410:{\displaystyle A\leq _{1}B\Rightarrow A\leq _{m}B\Rightarrow A\leq _{tt}B\Rightarrow A\leq _{wtt}B\Rightarrow A\leq _{T}B}
755:
178:
185:(a truth table) that, when given the answers to the queries, will produce the final answer of the reduction.
748:
624:
526:
39:
590:
31:
686:
296:). Considering also one-one reducibility, many-one reducibility and weak truth-table reducibility,
243:
564:
728:
444:
702:
694:
660:
570:
503:
471:
239:
182:
157:
126:
43:
732:
136:
108:
88:
68:
48:
197:
775:
181:
queries at the same time. In a truth-table reduction, the reduction also gives a
130:
17:
488:
is a total computable functional. To build the truth-table for computing
468:. The forward direction is trivial and for the reverse direction suppose
720:
677:. The forward direction fails for weak truth-table reducibility.
250:(bT) reductions rather than as weak truth-table (wtt) reductions.
621:
it is a simple matter to find the unique truth-table that gives
172:
by asking questions about the membership of various elements in
192:
691:
The Theory of
Recursive Functions and Effective Computability
258:
As every truth-table reduction is a Turing reduction, if
736:
209:
663:
627:
593:
573:
529:
506:
474:
447:
305:
246:. For this reason, they are sometimes referred to as
139:
111:
91:
71:
51:
669:
649:
609:
579:
551:
512:
480:
460:
409:
145:
117:
97:
77:
57:
168:computes the membership of a single element in
756:
8:
763:
749:
662:
632:
626:
598:
592:
572:
534:
528:
505:
473:
452:
446:
398:
373:
351:
332:
313:
304:
138:
110:
90:
70:
50:
105:, the reduction describes the answer to
27:Concept in theoretical computer science
156:Truth-table reductions are related to
7:
717:
715:
650:{\displaystyle \Gamma ^{\sigma }(n)}
552:{\displaystyle \Gamma ^{\sigma }(n)}
133:of some finite number of queries to
587:must be total on all paths through
693:, second edition 1987, MIT Press.
629:
574:
531:
475:
25:
500:such that for all binary strings
242:of the reduction is bounded by a
719:
196:
610:{\displaystyle 2^{<\omega }}
644:
638:
546:
540:
388:
363:
341:
322:
1:
496:) simply search for a number
735:. You can help Knowledge by
429:is truth-table reducible to
281:is also Turing reducible to
262:is truth-table reducible to
461:{\displaystyle 2^{\omega }}
229:Weak truth-table reductions
803:
714:
441:via a total functional on
235:weak truth-table reduction
787:Mathematical logic stubs
85:. To solve a problem in
670:{\displaystyle \sigma }
580:{\displaystyle \Gamma }
513:{\displaystyle \sigma }
481:{\displaystyle \Gamma }
437:is Turing reducible to
782:Reduction (complexity)
731:-related article is a
671:
651:
611:
581:
553:
514:
482:
462:
411:
147:
119:
99:
79:
65:to a decision problem
59:
672:
652:
612:
582:
554:
515:
483:
463:
412:
148:
120:
100:
80:
60:
36:truth-table reduction
661:
625:
591:
571:
559:converges. Such an
527:
504:
472:
445:
303:
137:
109:
89:
69:
49:
32:computability theory
244:computable function
729:mathematical logic
667:
647:
607:
577:
549:
510:
478:
458:
407:
208:. You can help by
143:
115:
95:
75:
55:
744:
743:
617:. Given such an
226:
225:
158:Turing reductions
146:{\displaystyle B}
118:{\displaystyle A}
98:{\displaystyle A}
78:{\displaystyle B}
58:{\displaystyle A}
16:(Redirected from
794:
765:
758:
751:
723:
716:
676:
674:
673:
668:
657:when applied to
656:
654:
653:
648:
637:
636:
616:
614:
613:
608:
606:
605:
586:
584:
583:
578:
558:
556:
555:
550:
539:
538:
519:
517:
516:
511:
487:
485:
484:
479:
467:
465:
464:
459:
457:
456:
416:
414:
413:
408:
403:
402:
384:
383:
359:
358:
337:
336:
318:
317:
221:
218:
200:
193:
152:
150:
149:
144:
124:
122:
121:
116:
104:
102:
101:
96:
84:
82:
81:
76:
64:
62:
61:
56:
44:decision problem
21:
802:
801:
797:
796:
795:
793:
792:
791:
772:
771:
770:
769:
712:
683:
659:
658:
628:
623:
622:
594:
589:
588:
569:
568:
530:
525:
524:
502:
501:
470:
469:
448:
443:
442:
433:if and only if
394:
369:
347:
328:
309:
301:
300:
292:
273:
256:
231:
222:
216:
213:
206:needs expansion
191:
183:boolean formula
135:
134:
127:boolean formula
107:
106:
87:
86:
67:
66:
47:
46:
28:
23:
22:
15:
12:
11:
5:
800:
798:
790:
789:
784:
774:
773:
768:
767:
760:
753:
745:
742:
741:
724:
710:
709:
687:H. Rogers, Jr.
682:
679:
666:
646:
643:
640:
635:
631:
604:
601:
597:
576:
563:must exist by
548:
545:
542:
537:
533:
509:
477:
455:
451:
419:
418:
406:
401:
397:
393:
390:
387:
382:
379:
376:
372:
368:
365:
362:
357:
354:
350:
346:
343:
340:
335:
331:
327:
324:
321:
316:
312:
308:
290:
271:
255:
252:
248:bounded Turing
230:
227:
224:
223:
203:
201:
190:
187:
142:
114:
94:
74:
54:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
799:
788:
785:
783:
780:
779:
777:
766:
761:
759:
754:
752:
747:
746:
740:
738:
734:
730:
725:
722:
718:
713:
708:
707:0-07-053522-1
704:
701:(paperback),
700:
699:0-262-68052-1
696:
692:
688:
685:
684:
680:
678:
664:
641:
633:
620:
602:
599:
595:
566:
565:Kőnig's lemma
562:
543:
535:
523:
507:
499:
495:
491:
453:
449:
440:
436:
432:
428:
425:Furthermore,
423:
404:
399:
395:
391:
385:
380:
377:
374:
370:
366:
360:
355:
352:
348:
344:
338:
333:
329:
325:
319:
314:
310:
306:
299:
298:
297:
295:
288:
284:
280:
276:
269:
265:
261:
253:
251:
249:
245:
241:
236:
228:
220:
211:
207:
204:This section
202:
199:
195:
194:
188:
186:
184:
180:
175:
171:
167:
163:
159:
154:
140:
132:
128:
112:
92:
72:
52:
45:
41:
38:is a type of
37:
33:
19:
737:expanding it
726:
711:
690:
618:
560:
521:
497:
493:
489:
438:
434:
430:
426:
424:
420:
293:
286:
282:
278:
274:
267:
263:
259:
257:
247:
234:
232:
214:
210:adding to it
205:
173:
169:
165:
161:
155:
35:
29:
18:Tt-reduction
131:truth table
776:Categories
681:References
520:of length
254:Properties
217:April 2024
189:Definition
665:σ
634:σ
630:Γ
603:ω
575:Γ
536:σ
532:Γ
508:σ
476:Γ
454:ω
396:≤
389:⇒
371:≤
364:⇒
349:≤
342:⇒
330:≤
323:⇒
311:≤
164:to a set
40:reduction
689:, 1967.
277:), then
289:≤
270:≤
42:from a
705:
697:
567:since
179:oracle
727:This
125:as a
733:stub
703:ISBN
695:ISBN
600:<
240:use
212:.
129:or
30:In
778::
272:tt
233:A
153:.
34:a
764:e
757:t
750:v
739:.
645:)
642:n
639:(
619:m
596:2
561:m
547:)
544:n
541:(
522:m
498:m
494:n
492:(
490:A
450:2
439:B
435:A
431:B
427:A
417:,
405:B
400:T
392:A
386:B
381:t
378:t
375:w
367:A
361:B
356:t
353:t
345:A
339:B
334:m
326:A
320:B
315:1
307:A
294:B
291:T
287:A
285:(
283:B
279:A
275:B
268:A
266:(
264:B
260:A
219:)
215:(
174:A
170:B
166:A
162:B
141:B
113:A
93:A
73:B
53:A
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
