43:
113:
717:, by considering the relationship between P and NP for an oracle A. In particular, it has been shown there exist languages A and B such that P=NP and P≠NP. The fact the P = NP question relativizes both ways is taken as evidence that answering this question is difficult, because a proof technique that
462:
Some definitions, instead of writing the answer to the oracle tape, have two special states YES and NO in addition to the ASK state. When the oracle is consulted, the next state is chosen to be YES if the contents of the oracle tape are in the oracle set, and chosen to the NO if the contents are not
756:
can determine whether particular Turing machines will halt on particular inputs, but it cannot determine, in general, whether machines equivalent to itself will halt. This creates a hierarchy of machines, each with a more powerful halting oracle and an even harder halting problem. This hierarchy of
466:
Some definitions eschew the separate oracle tape. When the oracle state is entered, a tape symbol is specified. The oracle is queried with the number of times that this tape symbol appears on the work tape. If that number is in the oracle set, the next state is the YES state; if it is not, the next
793:
answers each query randomly but consistently; the oracle is assumed to be available to all parties including the attacker, as the hash function is. Such a proof shows that unless the attacker solves the hard problem at the heart of the security reduction, they must make use of some interesting
478:
These definitions are equivalent from the point of view of Turing computability: a function is oracle-computable from a given oracle under all of these definitions if it is oracle-computable under any of them. The definitions are not equivalent, however, from the point of view of computational
357:
An oracle machine can perform all of the usual operations of a Turing machine, and can also query the oracle to obtain a solution to any instance of the computational problem for that oracle. For example, if the problem is a decision problem for a set
724:
One may consider the case where an oracle is chosen randomly from among all possible oracles (an infinite set). It has been shown in this case, that with probability 1, P≠NP. When a question is true for almost all oracles, it is said to be true
474:
of the oracle set is written on the oracle tape using symbols 0 and 1. The machine is then able to query the oracle by scanning to the correct square on the oracle tape and reading the value located there.
330:
of natural numbers (or strings). An instance of the problem is an arbitrary natural number (or string). The solution to the instance is "YES" if the number (string) is in the set, and "NO" otherwise.
706:
It is understood that NP ⊆ P, but the question of whether NP, P, NP, and P are equal remains tentative at best. It is believed they are different, and this leads to the definition of the
736:.) This is only weak evidence that P≠NP, since a statement may be true for a random oracle but false for ordinary Turing machines; for example, IP≠PSPACE for a random oracle A but
1025:
564:
407:, and which will perform different actions (reading data, writing data, moving the control mechanism, and changing states) depending on the current state and the data being read.
362:
of natural numbers, the oracle machine supplies the oracle with a natural number, and the oracle responds with "yes" or "no" stating whether that number is an element of
458:
There are many alternative definitions to the one presented above. Many of these are specialized for the case where the oracle solves a decision problem. In this case:
661:
606:
701:
681:
634:
1369:
573:
for some class B, then A=A provided that machines in A can execute reductions used in the completeness definition of class B. In particular, since SAT is
470:
Another alternative definition makes the oracle tape read-only, and eliminates the ASK and RESPONSE states entirely. Before the machine is started, the
1079:
433:
From time to time, the oracle machine may enter the ASK state. When this happens, the following actions are performed in a single computational step:
450:
The effect of changing to the ASK state is thus to receive, in a single step, a solution to the problem instance that is written on the oracle tape.
396:, which rests on a single cell of the work tape and can read the data there, write new data, and increment or decrement its position along the tape;
419:, which is a semi-infinite tape separate from the work tape. The alphabet for the oracle tape may be different from the alphabet for the work tape.
994:
732:. This choice of terminology is justified by the fact that random oracles support a statement with probability 0 or 1 only. (This follows from
318:. The problem does not have to be computable; the oracle is not assumed to be a Turing machine or computer program. The oracle is simply a "
1314:
479:
complexity. A definition such as the one by van
Melkebeek, using an oracle tape which may have its own alphabet, is required in general.
495:
solvable by an algorithm in class A with an oracle for a language L is called A. For example, P is the class of problems solvable in
794:
property of the hash function to break the protocol; they cannot treat the hash function as a black box (i.e., as a random oracle).
1398:
1257:
1211:
1182:
1102:
979:
389:: a sequence of cells without beginning or end, each of which may contain a B (for blank) or a symbol from the tape alphabet;
440:
the oracle is consulted, and the contents of the oracle tape are replaced with the solution to that instance of the problem;
237:
721:(i.e., unaffected by the addition of an oracle) will not answer the P = NP question. Most proof techniques relativize.
507:. The notation A can be extended to a set of languages B (or a complexity class B), by using the following definition:
86:
64:
374:
There are many equivalent definitions of oracle Turing machines, as discussed below. The one presented here is from
57:
733:
170:
513:
251:
1337:
1044:
504:
17:
1442:
1452:
1166:
1048:
500:
205:
426:
which, like the read/write head, can move left or right along the oracle tape reading and writing symbols;
337:
from natural numbers (or strings) to natural numbers (or strings). An instance of the problem is an input
782:
310:. The oracle, in this context, is an entity capable of solving some problem, which for example may be a
1173:
The
Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions
814:
51:
1447:
613:
230:
437:
the contents of the oracle tape are viewed as an instance of the oracle's computational problem;
31:
1307:
1199:
759:
609:
158:
68:
1361:
829:
570:
182:
707:
639:
584:
282:, which is able to solve certain problems in a single operation. The problem can be of any
255:
213:
194:
8:
1221:
781:, oracles are used to make arguments for the security of cryptographic protocols where a
287:
209:
166:
322:" that is able to produce a solution for any instance of a given computational problem:
1420:
686:
666:
619:
471:
223:
1171:
1149:
1412:
1404:
1394:
1356:
1291:
1263:
1253:
1233:
1207:
1178:
1154:
1098:
1071:
1017:
990:
975:
786:
174:
141:
1424:
1226:
1386:
1351:
1343:
1283:
1144:
1129:
1063:
1009:
809:
608:
given above is not completely standard. In some contexts, such as the proof of the
492:
488:
315:
311:
283:
267:
263:
178:
1282:. Perspectives in Mathematical Logic (1st ed.). Springer Berlin, Heidelberg.
1385:. Lecture Notes in Computer Science. Vol. 1950. Springer Berlin Heidelberg.
1379:
1275:
1121:
1097:. Studies in logic and the foundations of mathematics. Amsterdam: North-Holland.
804:
753:
737:
714:
496:
291:
1365:
1287:
1125:
683:
does not have any complete problems with respect to the reductions available to
1347:
1245:
1117:
819:
303:
271:
201:
1090:
1049:"Relative to a Random Oracle A, P != NP != co-NP with Probability 1"
1436:
1408:
1303:
1295:
1267:
1237:
1158:
1075:
1021:
824:
790:
772:
728:
1416:
789:
for the protocol is given in the case where, instead of a hash function, a
778:
1390:
1333:
574:
162:
145:
935:
1113:
616:, it is more useful to assume that the abstract machine defining class
713:
Oracle machines are useful for investigating the relationship between
636:
only has access to a single oracle for one language. In this context,
319:
275:
125:
104:
1067:
1013:
112:
578:
411:
In addition to these components, an oracle machine also includes:
577:
with respect to polynomial time reductions, P=P. However, if A =
443:
the oracle head is moved to the first square on the oracle tape;
871:
741:
887:
1111:
941:
1228:
Theory of recursive functions and effective computability
429:
two special states: the ASK state and the RESPONSE state.
1313:. CS254: Computational Complexity. Stanford University.
923:
482:
30:
For computing equipment sold by Oracle
Corporation, see
1381:
446:
the state of the oracle machine is changed to RESPONSE.
689:
669:
642:
622:
587:
516:
947:
911:
899:
859:
847:
381:
An oracle machine, like a Turing machine, includes:
1378:
1225:
1170:
695:
675:
655:
628:
600:
558:
1128:; Ranjan, Desh; Rohatgi, Pankaj (1 August 1994).
1434:
988:
893:
333:A function problem is represented by a function
27:Abstract machine used to study decision problems
766:
747:
1376:
1198:
581:, then A may not equal A. (The definition of
375:
231:
559:{\displaystyle A^{B}=\bigcup _{L\in B}A^{L}}
403:, which can be in one of a finite number of
1043:
929:
326:A decision problem is represented as a set
1206:. Reading, Massachusetts: Addison-Wesley.
453:
238:
224:
1355:
1250:Introduction to the theory of computation
1148:
87:Learn how and when to remove this message
1302:
917:
905:
302:An oracle machine can be conceived as a
50:This article includes a list of general
1280:Recursively Enumerable Sets and Degrees
1137:Journal of Computer and System Sciences
1130:"The random oracle hypothesis is false"
995:"Relativizations of the P=?NP Question"
663:is not defined if the complexity class
14:
1435:
1377:van Melkebeek, Dieter (29 June 2003).
1332:
1244:
1220:
1089:
1085:from the original on 25 December 2022.
969:
953:
881:
865:
853:
1274:
1165:
877:
483:Complexity classes of oracle machines
1342:(PhD thesis). Princeton University.
36:
1372:from the original on 13 March 2020.
757:machines can be used to define the
24:
1339:Systems of Logic Based on Ordinals
1177:. Hewlett, New York: Raven Press.
1031:from the original on 19 March 2023
56:it lacks sufficient corresponding
32:Oracle Corporation § Hardware
25:
1464:
1320:from the original on 1 April 2014
972:Foundations of computation theory
752:A machine with an oracle for the
1095:Computability, complexity, logic
111:
41:
1047:; Gill, John (February 1981).
894:Baker, Gill & Solovay 1975
505:Boolean satisfiability problem
369:
13:
1:
1150:10.1016/S0022-0000(05)80084-4
989:Baker, Theodore; Gill, John;
836:
841:
767:Applications to cryptography
748:Oracles and halting problems
501:deterministic Turing machine
345:. The solution is the value
270:. It can be visualized as a
7:
1288:10.1007/978-3-662-02460-7_3
797:
715:complexity classes P and NP
10:
1469:
1252:. Boston: PWS Publishing.
962:
770:
297:
29:
1357:21.11116/0000-0001-91CE-3
1232:. New York: McGraw-Hill.
1056:SIAM Journal on Computing
1002:SIAM Journal on Computing
734:Kolmogorov's zero–one law
219:
193:
188:
157:
152:
140:
135:
124:
119:
110:
103:
1348:10.1112/plms/s2-45.1.161
1204:Computational complexity
815:Interactive proof system
614:space hierarchy theorems
1200:Papadimitriou, Christos
930:Bennett & Gill 1981
503:with an oracle for the
454:Alternative definitions
71:more precise citations.
1169:, ed. (1 April 1965).
760:arithmetical hierarchy
697:
677:
657:
630:
602:
560:
467:state is the NO state.
136:Methods and techniques
1391:10.1007/3-540-44545-5
1308:"Notes for Lecture 4"
970:Adachi, Akeo (1990).
830:Padding oracle attack
698:
678:
658:
656:{\displaystyle A^{B}}
631:
603:
601:{\displaystyle A^{B}}
569:When a language L is
561:
214:Thermodynamic systems
183:System identification
1443:Computability theory
1202:(30 November 1993).
708:polynomial hierarchy
687:
667:
640:
620:
585:
514:
288:undecidable problems
256:computability theory
1453:Computation oracles
1306:(16 January 2014).
1045:Bennett, Charles H.
376:van Melkebeek (2003
210:Operations research
167:Pattern recognition
787:security reduction
693:
673:
653:
626:
598:
556:
545:
472:indicator function
463:in the oracle set.
153:Related techniques
1400:978-3-540-44545-6
1259:978-0-534-94728-6
1213:978-0-201-53082-7
1184:978-0-911216-01-1
1104:978-0-444-87406-1
993:(December 1975).
981:978-4-274-02190-9
974:. Tokyo: Ohmsha.
942:Chang et al. 1994
696:{\displaystyle A}
676:{\displaystyle B}
629:{\displaystyle A}
530:
493:decision problems
401:control mechanism
268:decision problems
252:complexity theory
248:
247:
175:White-box testing
142:Black-box testing
105:Black box systems
97:
96:
89:
16:(Redirected from
1460:
1428:
1384:
1373:
1359:
1329:
1327:
1325:
1319:
1312:
1299:
1276:Soare, Robert I.
1271:
1241:
1231:
1224:(1 April 1967).
1217:
1195:
1193:
1191:
1176:
1162:
1152:
1134:
1122:Hartmanis, Juris
1112:Chang, Richard;
1108:
1086:
1084:
1053:
1040:
1038:
1036:
1030:
999:
985:
957:
951:
945:
939:
933:
927:
921:
915:
909:
903:
897:
891:
885:
875:
869:
863:
857:
851:
810:Turing reduction
702:
700:
699:
694:
682:
680:
679:
674:
662:
660:
659:
654:
652:
651:
635:
633:
632:
627:
607:
605:
604:
599:
597:
596:
565:
563:
562:
557:
555:
554:
544:
526:
525:
489:complexity class
316:function problem
312:decision problem
306:connected to an
284:complexity class
264:abstract machine
240:
233:
226:
179:Gray-box testing
115:
101:
100:
92:
85:
81:
78:
72:
67:this article by
58:inline citations
45:
44:
37:
21:
1468:
1467:
1463:
1462:
1461:
1459:
1458:
1457:
1433:
1432:
1431:
1401:
1323:
1321:
1317:
1310:
1260:
1246:Sipser, Michael
1222:Rogers, Hartley
1214:
1189:
1187:
1185:
1132:
1118:Goldreich, Oded
1105:
1082:
1068:10.1137/0210008
1051:
1034:
1032:
1028:
1014:10.1137/0204037
997:
991:Solovay, Robert
982:
965:
960:
952:
948:
940:
936:
928:
924:
916:
912:
904:
900:
892:
888:
876:
872:
864:
860:
852:
848:
844:
839:
834:
805:Black box group
800:
775:
769:
754:halting problem
750:
688:
685:
684:
668:
665:
664:
647:
643:
641:
638:
637:
621:
618:
617:
592:
588:
586:
583:
582:
550:
546:
534:
521:
517:
515:
512:
511:
497:polynomial time
485:
456:
394:read/write head
378:, p. 43).
372:
300:
294:, can be used.
292:halting problem
244:
202:Control systems
148:
93:
82:
76:
73:
63:Please help to
62:
46:
42:
35:
28:
23:
22:
15:
12:
11:
5:
1466:
1456:
1455:
1450:
1448:Turing machine
1445:
1430:
1429:
1399:
1374:
1330:
1304:Trevisan, Luca
1300:
1272:
1258:
1242:
1218:
1212:
1196:
1183:
1163:
1109:
1103:
1087:
1041:
986:
980:
966:
964:
961:
959:
958:
956:, p. 141.
946:
934:
922:
910:
898:
896:, p. 431.
886:
884:, p. 130.
880:, p. 47;
870:
868:, p. 129.
858:
856:, p. 111.
845:
843:
840:
838:
835:
833:
832:
827:
822:
820:Matroid oracle
817:
812:
807:
801:
799:
796:
771:Main article:
768:
765:
749:
746:
692:
672:
650:
646:
625:
595:
591:
567:
566:
553:
549:
543:
540:
537:
533:
529:
524:
520:
484:
481:
476:
475:
468:
464:
455:
452:
448:
447:
444:
441:
438:
431:
430:
427:
420:
409:
408:
397:
390:
371:
368:
355:
354:
331:
304:Turing machine
299:
296:
290:, such as the
272:Turing machine
266:used to study
260:oracle machine
246:
245:
243:
242:
235:
228:
220:
217:
216:
191:
190:
186:
185:
155:
154:
150:
149:
138:
137:
133:
132:
130:Oracle machine
122:
121:
117:
116:
108:
107:
95:
94:
49:
47:
40:
26:
18:Relativization
9:
6:
4:
3:
2:
1465:
1454:
1451:
1449:
1446:
1444:
1441:
1440:
1438:
1426:
1422:
1418:
1414:
1410:
1406:
1402:
1396:
1392:
1388:
1383:
1382:
1375:
1371:
1367:
1363:
1358:
1353:
1349:
1345:
1341:
1340:
1335:
1331:
1316:
1309:
1305:
1301:
1297:
1293:
1289:
1285:
1281:
1277:
1273:
1269:
1265:
1261:
1255:
1251:
1247:
1243:
1239:
1235:
1230:
1229:
1223:
1219:
1215:
1209:
1205:
1201:
1197:
1186:
1180:
1175:
1174:
1168:
1167:Davis, Martin
1164:
1160:
1156:
1151:
1146:
1142:
1138:
1131:
1127:
1126:HĂĄstad, Johan
1123:
1119:
1115:
1110:
1106:
1100:
1096:
1092:
1088:
1081:
1077:
1073:
1069:
1065:
1061:
1057:
1050:
1046:
1042:
1027:
1023:
1019:
1015:
1011:
1007:
1003:
996:
992:
987:
983:
977:
973:
968:
967:
955:
950:
944:, p. 29.
943:
938:
932:, p. 96.
931:
926:
919:
918:Trevisan 2014
914:
907:
906:Trevisan 2014
902:
895:
890:
883:
879:
874:
867:
862:
855:
850:
846:
831:
828:
826:
825:Demand oracle
823:
821:
818:
816:
813:
811:
808:
806:
803:
802:
795:
792:
791:random oracle
788:
784:
783:hash function
780:
774:
773:Random oracle
764:
762:
761:
755:
745:
743:
739:
735:
731:
730:
729:random oracle
722:
720:
716:
711:
709:
704:
690:
670:
648:
644:
623:
615:
611:
593:
589:
580:
576:
572:
551:
547:
541:
538:
535:
531:
527:
522:
518:
510:
509:
508:
506:
502:
498:
494:
490:
480:
473:
469:
465:
461:
460:
459:
451:
445:
442:
439:
436:
435:
434:
428:
425:
421:
418:
414:
413:
412:
406:
402:
398:
395:
391:
388:
384:
383:
382:
379:
377:
367:
365:
361:
352:
348:
344:
340:
336:
332:
329:
325:
324:
323:
321:
317:
313:
309:
305:
295:
293:
289:
285:
281:
277:
273:
269:
265:
261:
257:
253:
241:
236:
234:
229:
227:
222:
221:
218:
215:
211:
207:
203:
199:
197:
192:
187:
184:
180:
176:
172:
168:
164:
160:
156:
151:
147:
143:
139:
134:
131:
127:
123:
118:
114:
109:
106:
102:
99:
91:
88:
80:
70:
66:
60:
59:
53:
48:
39:
38:
33:
19:
1380:
1338:
1334:Turing, Alan
1322:. Retrieved
1279:
1249:
1227:
1203:
1188:. Retrieved
1172:
1143:(1): 24–39.
1140:
1136:
1094:
1091:Börger, Egon
1059:
1055:
1033:. Retrieved
1005:
1001:
971:
949:
937:
925:
920:, p. 1.
913:
908:, p. 2.
901:
889:
873:
861:
849:
785:is used. A
779:cryptography
776:
758:
751:
726:
723:
718:
712:
705:
568:
486:
477:
457:
449:
432:
423:
416:
410:
404:
400:
393:
386:
380:
373:
363:
359:
356:
350:
346:
342:
338:
334:
327:
307:
301:
279:
278:, called an
259:
249:
206:Open systems
195:
189:Fundamentals
159:Feed forward
129:
98:
83:
77:October 2023
74:
55:
1114:Chor, Benny
954:Börger 1989
882:Rogers 1967
866:Rogers 1967
854:Adachi 1990
719:relativizes
575:NP-complete
424:oracle head
417:oracle tape
370:Definitions
198:information
163:Obfuscation
146:Blackboxing
69:introducing
1437:Categories
1324:22 October
1190:21 October
1035:21 October
878:Soare 1987
837:References
52:references
1409:1611-3349
1366:301792588
1296:0172-6641
1268:300459879
1238:559483934
1159:0022-0000
1076:0097-5397
1022:0097-5397
842:Footnotes
539:∈
532:⋃
387:work tape
320:black box
276:black box
171:White box
126:Black box
1425:27442913
1417:48909425
1370:Archived
1362:ProQuest
1336:(1939).
1315:Archived
1278:(1987).
1248:(1997).
1093:(1989).
1080:Archived
1026:Archived
798:See also
579:DLOGTIME
571:complete
196:A priori
963:Sources
298:Oracles
286:. Even
274:with a
65:improve
1423:
1415:
1407:
1397:
1364:
1294:
1266:
1256:
1236:
1210:
1181:
1157:
1101:
1074:
1020:
978:
742:PSPACE
727:for a
405:states
308:oracle
280:oracle
262:is an
120:System
54:, but
1421:S2CID
1318:(PDF)
1311:(PDF)
1133:(PDF)
1083:(PDF)
1062:(1).
1052:(PDF)
1029:(PDF)
1008:(4).
998:(PDF)
499:by a
314:or a
258:, an
1413:OCLC
1405:ISSN
1395:ISBN
1326:2023
1292:ISSN
1264:OCLC
1254:ISBN
1234:OCLC
1208:ISBN
1192:2023
1179:ISBN
1155:ISSN
1099:ISBN
1072:ISSN
1037:2023
1018:ISSN
976:ISBN
612:and
610:time
487:The
341:for
254:and
1387:doi
1352:hdl
1344:doi
1284:doi
1145:doi
1064:doi
1010:doi
777:In
703:.)
491:of
422:an
415:an
250:In
1439::
1419:.
1411:.
1403:.
1393:.
1368:.
1360:.
1350:.
1290:.
1262:.
1153:.
1141:49
1139:.
1135:.
1124:;
1120:;
1116:;
1078:.
1070:.
1060:10
1058:.
1054:.
1024:.
1016:.
1004:.
1000:.
763:.
744:.
740:=
738:IP
710:.
399:a
392:a
385:a
366:.
353:).
212:,
208:,
204:,
200:,
181:,
177:,
173:,
169:,
165:,
161:,
144:,
128:,
1427:.
1389::
1354::
1346::
1328:.
1298:.
1286::
1270:.
1240:.
1216:.
1194:.
1161:.
1147::
1107:.
1066::
1039:.
1012::
1006:4
984:.
691:A
671:B
649:B
645:A
624:A
594:B
590:A
552:L
548:A
542:B
536:L
528:=
523:B
519:A
364:A
360:A
351:x
349:(
347:f
343:f
339:x
335:f
328:A
239:e
232:t
225:v
90:)
84:(
79:)
75:(
61:.
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
