642:
proof system, where we have two all-powerful provers which communicate with a randomized polynomial-time verifier (but not with each other). If the string is in the language, they must be able to convince the verifier of this with high probability. If the string is not in the language, they must not
682:
Instead of simply giving the purported proof to the verifier on a tape, give it random access to the proof. The verifier can specify an index into the proof string and receive the corresponding bit. Since the verifier can write an index of polynomial length, it can potentially index into an
723:
that transforms instances of one to instances of the other with the same answer. Problems that are NEXPTIME-complete might be thought of as the hardest problems in NEXPTIME. We know that NEXPTIME-complete problems are not in NP; it has been proven that these problems cannot be verified in
743:. Succinct circuits are simple machines used to describe graphs in exponentially less space. They accept two vertex numbers as input and output whether there is an edge between them. If solving a problem on a graph in a natural representation, such as an
674:
can be seen as the class of problems where an all-powerful prover gives a purported proof that a string is in the language, and a deterministic polynomial-time machine verifies that it is a valid proof. We make two changes to this setup:
198:
755:-complete, because the input is exponentially smaller (under some mild condition that the NP-completeness reduction is achieved by a "projection"). As one simple example, finding a
80:
491:
386:
290:
534:
429:
324:
95:
740:
978:
948:
695:(poly, poly). What more, in this characterization the verifier may be limited to read only a constant number of bits, i.e.
716:
1340:
898:
704:
667:
971:
643:
be able to collaboratively trick the verifier into accepting the string except with low probability. The fact that
36:
687:
These two extensions together greatly extend the proof system's power, enabling it to recognize all languages in
17:
1375:
964:
651:
is quite impressive when we consider that when only one prover is present, we can only recognize all of
1356:
1163:
940:
656:
1345:
635:
715:
A decision problem is NEXPTIME-complete if it is in NEXPTIME, and every problem in NEXPTIME has a
42:
620:, the sets of natural numbers that can be recognized in NEXPTIME are exactly those that form the
450:
345:
249:
1299:
862:
800:
Juris
Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME.
729:
621:
617:
559:
498:
393:
1294:
1289:
193:{\displaystyle {\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})}
1284:
297:
850:
8:
866:
838:
878:
655:; the verifier's ability to "cross-examine" the two provers gives it great power. See
1304:
944:
894:
924:
1268:
1158:
1090:
1080:
987:
874:
846:
830:
756:
744:
583:
32:
21:
914:
1263:
1253:
1210:
1200:
1193:
1183:
1173:
1131:
1126:
1121:
1105:
1085:
1063:
1058:
1053:
1041:
1036:
1031:
1026:
934:
777:
772:
725:
597:
592:
573:
550:
208:
1258:
1146:
1068:
1021:
919:
909:
805:
588:
546:
1369:
930:
625:
1136:
1046:
818:
748:
751:, then solving the same problem on a succinct circuit representation is
1248:
1073:
842:
873:, Information and control, vol 71 num 3, décember 1986, pp. 181—185,
638:, where there are two major characterizations of it. The first is the
1243:
956:
720:
834:
1238:
1178:
1001:
821:(1974), "Turing machines and the spectra of first-order formulas",
679:
Add randomness, the ability to flip coins, to the verifier machine.
207:
can be defined using deterministic Turing machines as verifiers. A
1228:
782:
1335:
1330:
1205:
1188:
1325:
1320:
1141:
86:
1153:
1011:
1168:
1100:
1095:
1016:
1006:
501:
453:
396:
348:
300:
252:
98:
45:
719:to it. In other words, there is a polynomial-time
528:
485:
423:
380:
318:
284:
192:
74:
1367:
804:, volume 65, issue 2/3, pp.158–181. 1985.
662:Another interactive proof system characterizing
611:
972:
871:A note on succinct representations of graphs
936:Computational Complexity: A Modern Approach
816:
979:
965:
929:
647:proof systems can solve every problem in
142:
218:if and only if there exist polynomials
1368:
986:
162:
159:
156:
153:
150:
122:
119:
116:
113:
110:
107:
104:
101:
960:
226:, and a deterministic Turing machine
710:
13:
717:polynomial-time many-one reduction
705:probabilistically checkable proofs
668:probabilistically checkable proofs
14:
1387:
1341:Probabilistically checkable proof
683:exponentially long proof string.
553:⊆ EXPTIME ⊆ NEXPTIME
37:non-deterministic Turing machine
634:often arises in the context of
18:computational complexity theory
883:
856:
810:
794:
739:-complete problems relates to
517:
505:
478:
474:
466:
462:
412:
400:
373:
369:
361:
357:
313:
301:
277:
273:
265:
261:
187:
167:
65:
59:
1:
879:10.1016/S0019-9958(86)80009-2
788:
612:Alternative characterizations
759:for a graph thus encoded is
657:interactive proof system#MIP
75:{\displaystyle 2^{n^{O(1)}}}
7:
766:
596:if and only if there exist
10:
1392:
1357:List of complexity classes
628:of some logical sentence.
486:{\displaystyle 2^{q(|x|)}}
381:{\displaystyle 2^{q(|x|)}}
285:{\displaystyle 2^{p(|x|)}}
1354:
1313:
1277:
1221:
1114:
994:
636:interactive proof systems
1346:Interactive proof system
891:Computational Complexity
529:{\displaystyle M(x,y)=0}
424:{\displaystyle M(x,y)=1}
338:, there exists a string
35:that can be solved by a
901:. Section 20.1, pg.492.
802:Information and Control
1300:Arithmetical hierarchy
933:; Barak, Boaz (2009),
893:Addison-Wesley, 1994.
806:At ACM Digital Library
730:time hierarchy theorem
691:. The class is called
666:is a certain class of
624:, the set of sizes of
622:spectrum of a sentence
618:descriptive complexity
560:time hierarchy theorem
530:
487:
425:
382:
320:
286:
194:
76:
1295:Grzegorczyk hierarchy
1290:Exponential hierarchy
1222:Considered infeasible
531:
488:
426:
383:
321:
319:{\displaystyle (x,y)}
287:
195:
77:
1285:Polynomial hierarchy
1115:Suspected infeasible
735:An important set of
499:
451:
394:
346:
298:
250:
96:
43:
1314:Families of classes
995:Considered feasible
586:); more precisely,
1376:Complexity classes
988:Complexity classes
889:C. Papadimitriou.
707:for more details.
659:for more details.
580:NEXPTIME = EXPTIME
526:
483:
421:
378:
316:
282:
190:
147:
72:
27:(sometimes called
1363:
1362:
1305:Boolean hierarchy
1278:Class hierarchies
950:978-0-521-42426-4
741:succinct circuits
711:NEXPTIME-complete
558:and also, by the
130:
33:decision problems
1383:
981:
974:
967:
958:
957:
953:
902:
887:
881:
863:C. Papadimitriou
860:
854:
853:
817:Jones, Neil D.;
814:
808:
798:
757:Hamiltonian path
745:adjacency matrix
604:that are not in
598:sparse languages
595:
584:padding argument
581:
576:
568:
554:
537:
535:
533:
532:
527:
492:
490:
489:
484:
482:
481:
477:
469:
443:and all strings
432:
430:
428:
427:
422:
387:
385:
384:
379:
377:
376:
372:
364:
327:
325:
323:
322:
317:
291:
289:
288:
283:
281:
280:
276:
268:
199:
197:
196:
191:
186:
185:
184:
183:
166:
165:
146:
145:
126:
125:
81:
79:
78:
73:
71:
70:
69:
68:
31:) is the set of
22:complexity class
1391:
1390:
1386:
1385:
1384:
1382:
1381:
1380:
1366:
1365:
1364:
1359:
1350:
1309:
1273:
1217:
1211:PSPACE-complete
1110:
990:
985:
951:
905:
888:
884:
861:
857:
835:10.2307/2272354
819:Selman, Alan L.
815:
811:
799:
795:
791:
773:Game complexity
769:
726:polynomial time
713:
703:(poly, 1). See
614:
587:
579:
574:
566:
545:
500:
497:
496:
494:
473:
465:
458:
454:
452:
449:
448:
395:
392:
391:
389:
368:
360:
353:
349:
347:
344:
343:
299:
296:
295:
293:
272:
264:
257:
253:
251:
248:
247:
203:Alternatively,
179:
175:
174:
170:
149:
148:
141:
134:
100:
99:
97:
94:
93:
55:
51:
50:
46:
44:
41:
40:
12:
11:
5:
1389:
1379:
1378:
1361:
1360:
1355:
1352:
1351:
1349:
1348:
1343:
1338:
1333:
1328:
1323:
1317:
1315:
1311:
1310:
1308:
1307:
1302:
1297:
1292:
1287:
1281:
1279:
1275:
1274:
1272:
1271:
1266:
1261:
1256:
1251:
1246:
1241:
1236:
1231:
1225:
1223:
1219:
1218:
1216:
1215:
1214:
1213:
1203:
1198:
1197:
1196:
1186:
1181:
1176:
1171:
1166:
1161:
1156:
1151:
1150:
1149:
1147:co-NP-complete
1144:
1139:
1134:
1124:
1118:
1116:
1112:
1111:
1109:
1108:
1103:
1098:
1093:
1088:
1083:
1078:
1077:
1076:
1066:
1061:
1056:
1051:
1050:
1049:
1039:
1034:
1029:
1024:
1019:
1014:
1009:
1004:
998:
996:
992:
991:
984:
983:
976:
969:
961:
955:
954:
949:
943:, p. 57,
931:Arora, Sanjeev
927:
920:Complexity Zoo
910:Complexity Zoo
904:
903:
882:
855:
829:(1): 139–150,
809:
792:
790:
787:
786:
785:
780:
775:
768:
765:
712:
709:
685:
684:
680:
670:. Recall that
613:
610:
570:
569:
556:
555:
539:
538:
525:
522:
519:
516:
513:
510:
507:
504:
480:
476:
472:
468:
464:
461:
457:
433:
420:
417:
414:
411:
408:
405:
402:
399:
375:
371:
367:
363:
359:
356:
352:
328:
315:
312:
309:
306:
303:
279:
275:
271:
267:
263:
260:
256:
242:, the machine
201:
200:
189:
182:
178:
173:
169:
164:
161:
158:
155:
152:
144:
140:
137:
133:
129:
124:
121:
118:
115:
112:
109:
106:
103:
67:
64:
61:
58:
54:
49:
9:
6:
4:
3:
2:
1388:
1377:
1374:
1373:
1371:
1358:
1353:
1347:
1344:
1342:
1339:
1337:
1334:
1332:
1329:
1327:
1324:
1322:
1319:
1318:
1316:
1312:
1306:
1303:
1301:
1298:
1296:
1293:
1291:
1288:
1286:
1283:
1282:
1280:
1276:
1270:
1267:
1265:
1262:
1260:
1257:
1255:
1252:
1250:
1247:
1245:
1242:
1240:
1237:
1235:
1232:
1230:
1227:
1226:
1224:
1220:
1212:
1209:
1208:
1207:
1204:
1202:
1199:
1195:
1192:
1191:
1190:
1187:
1185:
1182:
1180:
1177:
1175:
1172:
1170:
1167:
1165:
1162:
1160:
1157:
1155:
1152:
1148:
1145:
1143:
1140:
1138:
1135:
1133:
1130:
1129:
1128:
1125:
1123:
1120:
1119:
1117:
1113:
1107:
1104:
1102:
1099:
1097:
1094:
1092:
1089:
1087:
1084:
1082:
1079:
1075:
1072:
1071:
1070:
1067:
1065:
1062:
1060:
1057:
1055:
1052:
1048:
1045:
1044:
1043:
1040:
1038:
1035:
1033:
1030:
1028:
1025:
1023:
1020:
1018:
1015:
1013:
1010:
1008:
1005:
1003:
1000:
999:
997:
993:
989:
982:
977:
975:
970:
968:
963:
962:
959:
952:
946:
942:
938:
937:
932:
928:
926:
922:
921:
916:
912:
911:
907:
906:
900:
899:0-201-53082-1
896:
892:
886:
880:
876:
872:
868:
867:M. Yannakakis
864:
859:
852:
848:
844:
840:
836:
832:
828:
824:
823:J. Symb. Log.
820:
813:
807:
803:
797:
793:
784:
781:
779:
776:
774:
771:
770:
764:
762:
758:
754:
750:
746:
742:
738:
733:
731:
727:
722:
718:
708:
706:
702:
698:
694:
690:
681:
678:
677:
676:
673:
669:
665:
660:
658:
654:
650:
646:
641:
637:
633:
629:
627:
626:finite models
623:
619:
609:
607:
603:
599:
594:
590:
585:
577:
567:NP ⊊ NEXPTIME
565:
564:
563:
561:
552:
548:
544:
543:
542:
523:
520:
514:
511:
508:
502:
470:
459:
455:
446:
442:
438:
434:
418:
415:
409:
406:
403:
397:
365:
354:
350:
341:
337:
333:
329:
310:
307:
304:
269:
258:
254:
246:runs in time
245:
241:
237:
233:
232:
231:
229:
225:
221:
217:
213:
210:
206:
180:
176:
171:
138:
135:
131:
127:
92:
91:
90:
88:
83:
62:
56:
52:
47:
38:
34:
30:
26:
23:
19:
1233:
935:
918:
908:
890:
885:
870:
858:
826:
822:
812:
801:
796:
760:
752:
736:
734:
714:
700:
696:
692:
688:
686:
671:
663:
661:
652:
648:
644:
639:
631:
630:
615:
605:
601:
571:
557:
540:
444:
440:
436:
339:
335:
331:
243:
239:
235:
230:, such that
227:
223:
219:
215:
211:
204:
202:
85:In terms of
84:
28:
24:
15:
1194:#P-complete
1132:NP-complete
1047:NL-complete
763:-complete.
749:NP-complete
39:using time
1249:ELEMENTARY
1074:P-complete
851:0288.02021
789:References
447:of length
388:such that
342:of length
1244:2-EXPTIME
941:Cambridge
728:, by the
721:algorithm
292:on input
139:∈
132:⋃
1370:Category
1239:EXPSPACE
1234:NEXPTIME
1002:DLOGTIME
767:See also
761:NEXPTIME
753:NEXPTIME
737:NEXPTIME
697:NEXPTIME
689:NEXPTIME
664:NEXPTIME
649:NEXPTIME
632:NEXPTIME
549:⊆
541:We know
435:For all
330:For all
234:For all
216:NEXPTIME
209:language
205:NEXPTIME
25:NEXPTIME
1229:EXPTIME
1137:NP-hard
843:2272354
783:EXPTIME
578:, then
562:, that
536:
495:
439:not in
431:
390:
326:
294:
1336:NSPACE
1331:DSPACE
1206:PSPACE
947:
925:coNEXP
897:
865:&
849:
841:
653:PSPACE
575:P = NP
214:is in
20:, the
1326:NTIME
1321:DTIME
1142:co-NP
839:JSTOR
747:, is
87:NTIME
1154:TFNP
945:ISBN
915:NEXP
895:ISBN
238:and
222:and
29:NEXP
1269:ALL
1169:QMA
1159:FNP
1101:APX
1096:BQP
1091:BPP
1081:ZPP
1012:ACC
875:doi
847:Zbl
831:doi
701:PCP
693:PCP
645:MIP
640:MIP
616:In
600:in
572:If
334:in
16:In
1372::
1264:RE
1254:PR
1201:IP
1189:#P
1184:PP
1179:⊕P
1174:PH
1164:AM
1127:NP
1122:UP
1106:FP
1086:RP
1064:CC
1059:SC
1054:NC
1042:NL
1037:FL
1032:RL
1027:SL
1017:TC
1007:AC
939:,
923::
917:,
913::
869:,
845:,
837:,
827:39
825:,
778:NP
732:.
699:=
672:NP
608:.
602:NP
593:NE
591:≠
551:NP
493:,
89:,
82:.
1259:R
1069:P
1022:L
980:e
973:t
966:v
877::
833::
606:P
589:E
582:(
547:P
524:0
521:=
518:)
515:y
512:,
509:x
506:(
503:M
479:)
475:|
471:x
467:|
463:(
460:q
456:2
445:y
441:L
437:x
419:1
416:=
413:)
410:y
407:,
404:x
401:(
398:M
374:)
370:|
366:x
362:|
358:(
355:q
351:2
340:y
336:L
332:x
314:)
311:y
308:,
305:x
302:(
278:)
274:|
270:x
266:|
262:(
259:p
255:2
244:M
240:y
236:x
228:M
224:q
220:p
212:L
188:)
181:k
177:n
172:2
168:(
163:E
160:M
157:I
154:T
151:N
143:N
136:k
128:=
123:E
120:M
117:I
114:T
111:P
108:X
105:E
102:N
66:)
63:1
60:(
57:O
53:n
48:2
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.