90:
25:
621:
By repeated random selection of a possible witness, the large probability that a random string is a witness gives an expected polynomial time algorithm for accepting or rejecting an input. Conversely, if the Turing
Machine is expected polynomial-time (for any given x), then a considerable fraction of
577:
with a second input tape for V on which is written the sequence of coin flips. By selecting the witness as a random string, the verifier is a probabilistic polynomial-time Turing
Machine whose probability of accepting x when x is in
353:, the chance that it will yield an answer before we stop it is at least 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is at most 1/2, fitting the definition of an
481:
The witness need not be a traditionally construed proof. If V is a probabilistic Turing machine which could possibly accept x if x is in X, then the proof is the string of coin flips which leads the machine to accept
289:
Given an input, run A on the input for one step. If it returns YES, the answer must be YES. Otherwise, run B on the input for one step. If it returns NO, the answer must be NO. If neither occurs, repeat this
294:
Note that only one machine can ever give a wrong answer, and the chance of that machine giving the wrong answer during each repetition is at most 50%. This means that the chance of reaching the
675:
for itself, meaning that a ZPP machine with the power to solve ZPP problems instantly (a ZPP oracle machine) is not any more powerful than the machine without this extra power. In symbols,
475:
The definition is very asymmetric. The proof of x being in X is a single string. The proof of x not being in X is the collection of all strings, none of which is a proof of membership.
454:
can be thought of as the proof of membership. In the case of short proofs (of length bounded by a polynomial in the size of the input) which can be efficiently verified (
54:
152:
In other words, if the algorithm is allowed to flip a truly-random coin while it is running, it will always return the correct answer and, for a problem of size
862:
1259:
656:
language has V(x,w) accept on a (clear) majority of strings w if x is in X, and conversely reject on a (clear) majority of strings w if x is not in
213:
513:
a polynomial, only one need cause the verifier to accept (if x is in X. If x is not in X, no string will cause the verifier to accept).
1224:
76:
855:
535:
is the class of sets for which any random string is likely to be a witness of x in X, or x not in X, which ever the case may be.
122:
345:
its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO.
531:
is the class of sets for which, if x is not in X, any randomly chosen string is likely to be a witness for non-membership.
184:
138:
37:
848:
211:
is based on probabilistic Turing machines, but, for clarity, note that other complexity classes based on them include
1047:
47:
41:
33:
1240:
660:. No single string w need be definitive, and therefore they cannot in general be considered proofs or witnesses.
58:
1229:
1183:
796:
350:
1178:
1173:
200:
It returns DO NOT KNOW with probability at most 1/2 for every input (and the correct answer otherwise).
622:
the runs must be polynomial-time bounded, and the coin sequence used in such a run will be a witness.
1168:
271:
173:
89:
333:, suppose we have a Las Vegas algorithm C to solve a problem. We can then construct the following
1188:
1152:
1042:
974:
871:
809:
672:
230:
134:
98:
1077:
509:
requires only that witnesses exist. They may be very rare. Of the 2 possible strings, with
1147:
1137:
1094:
1084:
1067:
1057:
1015:
1010:
1005:
989:
969:
947:
942:
937:
925:
920:
915:
910:
816:
247:
219:
130:
106:
94:
486:(provided all members in X have some witness and the machine never accepts a non-member).
1142:
1030:
952:
905:
830:
740:
303:
110:
1253:
172:), even though it might occasionally be much longer. Such an algorithm is called a
756:, i.e., every Las Vegas algorithm has a deterministic polynomial-time equivalent.
835:
489:
The co-concept is a proof of non-membership, or membership in the complement set.
1020:
930:
1132:
957:
527:
The corresponding co-classes have witness for non-membership. In particular,
1127:
1122:
1117:
1062:
885:
668:
It is known that ZPP is closed under complement; that is, ZPP = co-ZPP.
1112:
775:
765:
1072:
1219:
1214:
1089:
840:
636:
does not require witnesses, although witnesses are sufficient (hence
114:
361:
algorithm is identical, except that it gives YES if C "times out".
1209:
1204:
1025:
561:) corresponds to the deterministic polynomial-time Turing Machine
88:
1037:
895:
614:
is large, but zero of incorrectly accepting or rejecting x (for
844:
458:
is a polynomial-time deterministic Turing machine), the string
1052:
984:
979:
900:
890:
478:
For all x in X there must be a witness to its membership in X.
225:
197:
The answer is always either DO NOT KNOW or the correct answer.
148:
The running time is polynomial in expectation for every input.
102:
18:
381:
can be thought of in terms of proof of membership in a set.
93:
ZPP in relation to other probabilistic complexity classes (
594:); of rejecting x when x is not in X is large but zero if
550:
is easy. The probabilistic polynomial-time Turing
Machine
259:. To show this, first note that every problem which is in
505:
are sets which have witnesses for membership. The class
117:. It is unknown if any of these containments are strict.
164:) such that the average running time will be less than
524:
any string chosen at random will likely be a witness.
748:, and some computer scientists have conjectured that
538:
Connecting this definition with other definitions of
282:
algorithm A and the (possibly completely different)
278:
Suppose we have a language L recognized by both the
245:
is exactly equal to the intersection of the classes
183:
can be defined as the class of problems for which a
1197:
1161:
1105:
998:
878:
229:is based on another machine with randomness: the
46:but its sources remain unclear because it lacks
145:It always returns the correct YES or NO answer.
582:is large (greater than 1/2, say), but zero if
255:. This is often taken to be the definition of
856:
391:V for a set X is a Turing machine such that:
8:
306:running time is polynomial. This shows that
194:It returns an answer YES, NO or DO NOT KNOW.
606:); and of correctly accepting or rejecting
863:
849:
841:
759:There exists an oracle relative to which
77:Learn how and when to remove this message
7:
204:The two definitions are equivalent.
573:) by replacing the random tape of
298:th round shrinks exponentially in
191:It always runs in polynomial time.
14:
1225:Probabilistically checkable proof
1260:Probabilistic complexity classes
23:
727:is obviously contained in both
664:Complexity-theoretic properties
187:exists with these properties:
141:exists with these properties:
1:
185:probabilistic Turing machine
139:probabilistic Turing machine
707:Connection to other classes
403:then there exists a string
156:, there is some polynomial
16:Concept in computer science
1276:
1241:List of complexity classes
628:should be contrasted with
129:(zero-error probabilistic
1238:
1230:Interactive proof system
137:of problems for which a
32:This article includes a
430:, then for all strings
237:Intersection definition
61:more precise citations.
1184:Arithmetical hierarchy
797:time hierarchy theorem
118:
1179:Grzegorczyk hierarchy
1174:Exponential hierarchy
1106:Considered infeasible
92:
1169:Polynomial hierarchy
999:Suspected infeasible
109:), which generalise
1198:Families of classes
879:Considered feasible
351:Markov's Inequality
341:Run C for at least
302:, showing that the
272:Las Vegas algorithm
174:Las Vegas algorithm
872:Complexity classes
207:The definition of
119:
34:list of references
1247:
1246:
1189:Boolean hierarchy
1162:Class hierarchies
779:would imply that
365:Witness and proof
123:complexity theory
87:
86:
79:
1267:
865:
858:
851:
842:
744:is contained in
699:is contained in
516:For the classes
325:is contained in
314:is contained in
231:quantum computer
135:complexity class
82:
75:
71:
68:
62:
57:this article by
48:inline citations
27:
26:
19:
1275:
1274:
1270:
1269:
1268:
1266:
1265:
1264:
1250:
1249:
1248:
1243:
1234:
1193:
1157:
1101:
1095:PSPACE-complete
994:
874:
869:
826:
805:
709:
666:
610:as a member of
555:
367:
357:algorithm. The
239:
179:Alternatively,
131:polynomial time
83:
72:
66:
63:
52:
38:related reading
28:
24:
17:
12:
11:
5:
1273:
1271:
1263:
1262:
1252:
1251:
1245:
1244:
1239:
1236:
1235:
1233:
1232:
1227:
1222:
1217:
1212:
1207:
1201:
1199:
1195:
1194:
1192:
1191:
1186:
1181:
1176:
1171:
1165:
1163:
1159:
1158:
1156:
1155:
1150:
1145:
1140:
1135:
1130:
1125:
1120:
1115:
1109:
1107:
1103:
1102:
1100:
1099:
1098:
1097:
1087:
1082:
1081:
1080:
1070:
1065:
1060:
1055:
1050:
1045:
1040:
1035:
1034:
1033:
1031:co-NP-complete
1028:
1023:
1018:
1008:
1002:
1000:
996:
995:
993:
992:
987:
982:
977:
972:
967:
962:
961:
960:
950:
945:
940:
935:
934:
933:
923:
918:
913:
908:
903:
898:
893:
888:
882:
880:
876:
875:
870:
868:
867:
860:
853:
845:
839:
838:
831:Complexity Zoo
825:
824:External links
822:
821:
820:
813:
804:
801:
769:. A proof for
708:
705:
665:
662:
553:
491:
490:
487:
479:
476:
448:
447:
420:
366:
363:
347:
346:
292:
291:
287:
238:
235:
202:
201:
198:
195:
192:
150:
149:
146:
85:
84:
42:external links
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
1272:
1261:
1258:
1257:
1255:
1242:
1237:
1231:
1228:
1226:
1223:
1221:
1218:
1216:
1213:
1211:
1208:
1206:
1203:
1202:
1200:
1196:
1190:
1187:
1185:
1182:
1180:
1177:
1175:
1172:
1170:
1167:
1166:
1164:
1160:
1154:
1151:
1149:
1146:
1144:
1141:
1139:
1136:
1134:
1131:
1129:
1126:
1124:
1121:
1119:
1116:
1114:
1111:
1110:
1108:
1104:
1096:
1093:
1092:
1091:
1088:
1086:
1083:
1079:
1076:
1075:
1074:
1071:
1069:
1066:
1064:
1061:
1059:
1056:
1054:
1051:
1049:
1046:
1044:
1041:
1039:
1036:
1032:
1029:
1027:
1024:
1022:
1019:
1017:
1014:
1013:
1012:
1009:
1007:
1004:
1003:
1001:
997:
991:
988:
986:
983:
981:
978:
976:
973:
971:
968:
966:
963:
959:
956:
955:
954:
951:
949:
946:
944:
941:
939:
936:
932:
929:
928:
927:
924:
922:
919:
917:
914:
912:
909:
907:
904:
902:
899:
897:
894:
892:
889:
887:
884:
883:
881:
877:
873:
866:
861:
859:
854:
852:
847:
846:
843:
837:
836:ZPP Class ZPP
833:
832:
828:
827:
823:
819:
818:
814:
812:
811:
807:
806:
802:
800:
798:
794:
790:
786:
782:
778:
777:
772:
768:
767:
762:
757:
755:
751:
747:
743:
742:
736:
734:
730:
726:
722:
718:
714:
706:
704:
702:
698:
694:
692:
688:
684:
682:
678:
674:
669:
663:
661:
659:
655:
651:
647:
643:
639:
635:
631:
627:
623:
619:
617:
613:
609:
605:
601:
597:
593:
589:
585:
581:
576:
572:
568:
564:
560:
556:
549:
545:
541:
536:
534:
530:
525:
523:
519:
514:
512:
508:
504:
500:
496:
488:
485:
480:
477:
474:
473:
472:
471:
467:
465:
461:
457:
453:
445:
441:
437:
433:
429:
425:
421:
418:
414:
410:
406:
402:
398:
394:
393:
392:
390:
386:
382:
380:
376:
372:
364:
362:
360:
356:
352:
344:
340:
339:
338:
336:
332:
328:
324:
321:To show that
319:
317:
313:
309:
305:
301:
297:
288:
285:
281:
277:
276:
275:
273:
269:
265:
262:
258:
254:
250:
249:
244:
236:
234:
232:
228:
227:
223:. The class
222:
221:
216:
215:
210:
205:
199:
196:
193:
190:
189:
188:
186:
182:
177:
175:
171:
167:
163:
159:
155:
147:
144:
143:
142:
140:
136:
132:
128:
124:
116:
112:
108:
104:
100:
96:
91:
81:
78:
70:
60:
56:
50:
49:
43:
39:
35:
30:
21:
20:
964:
829:
815:
808:
792:
788:
784:
780:
774:
770:
764:
760:
758:
753:
749:
745:
739:
737:
732:
728:
724:
720:
716:
712:
710:
700:
696:
695:
690:
686:
685:
680:
676:
670:
667:
657:
653:
649:
645:
641:
637:
633:
632:. The class
629:
625:
624:
620:
615:
611:
607:
603:
599:
595:
591:
587:
583:
579:
574:
570:
566:
562:
558:
551:
547:
543:
539:
537:
532:
528:
526:
521:
517:
515:
510:
506:
502:
498:
494:
493:The classes
492:
483:
469:
468:
463:
462:is called a
459:
455:
451:
449:
443:
439:
435:
431:
427:
423:
416:
412:
408:
404:
400:
396:
388:
384:
383:
378:
374:
370:
369:The classes
368:
358:
354:
348:
342:
334:
330:
326:
322:
320:
315:
311:
307:
299:
295:
293:
286:algorithm B.
283:
279:
274:as follows:
267:
263:
260:
256:
252:
246:
242:
240:
224:
218:
212:
208:
206:
203:
180:
178:
169:
165:
161:
157:
153:
151:
126:
120:
73:
67:January 2013
64:
53:Please help
45:
1078:#P-complete
1016:NP-complete
931:NL-complete
450:The string
385:Definition:
337:algorithm:
59:introducing
1133:ELEMENTARY
958:P-complete
738:The class
446:) rejects.
426:is not in
419:) accepts;
407:such that
329:intersect
310:intersect
241:The class
1128:2-EXPTIME
640:contains
133:) is the
97:, co-RP,
1254:Category
1123:EXPSPACE
1118:NEXPTIME
886:DLOGTIME
803:See also
389:verifier
304:expected
1113:EXPTIME
1021:NP-hard
793:EXPTIME
776:EXPTIME
766:EXPTIME
671:ZPP is
464:witness
113:within
55:improve
1220:NSPACE
1215:DSPACE
1090:PSPACE
711:Since
470:Notes:
399:is in
343:double
270:has a
115:PSPACE
1210:NTIME
1205:DTIME
1026:co-NP
795:(see
787:, as
652:). A
646:co-RP
604:co-RP
602:(for
590:(for
544:co-RP
529:co-RP
359:co-RP
331:co-RP
312:co-RP
290:step.
284:co-RP
268:co-RP
253:co-RP
40:, or
1038:TFNP
733:coRP
731:and
721:coRP
648:and
546:and
520:and
501:and
377:and
266:and
261:both
251:and
217:and
1153:ALL
1053:QMA
1043:FNP
985:APX
980:BQP
975:BPP
965:ZPP
896:ACC
810:BPP
799:).
785:ZPP
771:ZPP
761:ZPP
754:ZPP
746:ZPP
725:ZPP
713:ZPP
701:ZPP
691:ZPP
687:ZPP
681:ZPP
677:ZPP
673:low
654:BPP
650:ZPP
638:BPP
634:BPP
630:BPP
626:ZPP
618:).
616:ZPP
548:ZPP
533:ZPP
522:ZPP
503:ZPP
466:.
422:if
395:if
379:ZPP
349:By
323:ZPP
316:ZPP
257:ZPP
243:ZPP
226:BQP
214:BPP
209:ZPP
181:ZPP
127:ZPP
121:In
103:BQP
99:BPP
1256::
1148:RE
1138:PR
1085:IP
1073:#P
1068:PP
1063:⊕P
1058:PH
1048:AM
1011:NP
1006:UP
990:FP
970:RP
948:CC
943:SC
938:NC
926:NL
921:FL
916:RL
911:SL
901:TC
891:AC
834::
817:RP
791:≠
783:≠
773:=
763:=
752:=
735:.
729:RP
723:,
719:∩
717:RP
715:=
703:.
697:NP
693:.
689:=
683:.
679:=
644:,
642:RP
598:∈
592:RP
586:∉
575:V*
569:,
552:V*
542:,
540:RP
518:RP
507:NP
499:RP
497:,
495:NP
434:,
387:A
375:RP
373:,
371:NP
355:RP
335:RP
327:RP
318:.
308:RP
280:RP
264:RP
248:RP
233:.
220:RP
176:.
125:,
107:PP
105:,
101:,
95:RP
44:,
36:,
1143:R
953:P
906:L
864:e
857:t
850:v
789:P
781:P
750:P
741:P
658:X
612:X
608:x
600:X
596:x
588:X
584:x
580:X
571:w
567:x
565:(
563:V
559:x
557:(
554:w
511:f
484:x
460:w
456:V
452:w
444:w
442:,
440:x
438:(
436:V
432:w
428:X
424:x
417:w
415:,
413:x
411:(
409:V
405:w
401:X
397:x
300:k
296:k
170:n
168:(
166:p
162:n
160:(
158:p
154:n
111:P
80:)
74:(
69:)
65:(
51:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
