300:= 1/2: if the NP problem's answer is yes, then every constraint (which corresponds to a particular value for the random bits) has a satisfying assignment (an acceptable proof); otherwise, any proof should be rejected with probability at least 1/2, which means any assignment must satisfy fewer than 1/2 of the constraints (which means it will be accepted with probability lower than 1/2). Therefore, an algorithm for the promise problem would be able to solve the underlying NP problem, and hence the promise problem must be NP hard.
882:
Dorit
Aharonov, a professor of computer science and engineering at Hebrew University in Jerusalem, says that Vidick and Ito's paper is the quantum analogue of an earlier paper on multiprover interactive proofs that "basically led to the PCP theorem, and the PCP theorem is no doubt the most important
580:
In 2012, Thomas Vidick and
Tsuyoshi Ito published a result that showed a "strong limitation on the ability of entangled provers to collude in a multiplayer game". This could be a step toward proving the quantum analogue of the PCP theorem, since when the result was reported in the media, professor
883:
result of complexity in the past 20 years." Similarly, she says, the new paper "could be an important step toward proving the quantum analogue of the PCP theorem, which is a major open question in quantum complexity theory."
614:)-bit classical communications, and the completeness is c and the soundness is s. They also showed that the Hamiltonian version of a quantum PCP conjecture, namely a local Hamiltonian problem with constant promise gap
327:. This can be done by reducing the problem of approximating a solution to such problems to a promise problem of the above form. These results are sometimes also called PCP theorems because they can be viewed as
850:
Interactive proofs are the basis of cryptographic systems now in wide use, but for computer scientists, they're just as important for the insight they provide into the complexity of computational problems.
404:
870:
1305:
764:
189:: the choice of bits of the proof to check depend only on the random bits and the description of the problem instance, not the actual bits of the proof.
420:
and probabilistically checkable proofs. The first theorem relating standard proofs and probabilistically checkable proofs is the statement that
838:
1190:
1164:
930:
701:
674:
866:
1310:
1006:
748:
588:
In 2018, Thomas Vidick and Anand
Natarajan proved a games variant of quantum PCP theorem under randomized reduction. It states that
476:
465:
328:
162:
149:
61:
585:
called it "the quantum analogue of an earlier paper on multiprover interactive proofs" that "basically led to the PCP theorem".
258:
198:
38:
895:
Natarajan, A.; Vidick, T. (October 2018). "Low-Degree
Testing for Quantum States, and a Quantum Entangled Games PCP for QMA".
1300:
344:
304:
303:
As a consequence of this theorem, it can be shown that the solutions to many natural optimization problems including maximum
634:
was a fundamental unresolved obstacle and precursor to a quantum analog of PCP. The NLTS conjecture was proven in 2022 by
181:) bits of the proof, correct proofs are always accepted, and incorrect proofs are rejected with probability at least 1/2.
784:
31:
802:
53rd Annual IEEE Symposium on
Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20–23, 2012
468:. The notation is that of a function that returns a certain complexity class. See the explanation mentioned above.
800:
Ito, Tsuyoshi; Vidick, Thomas (2012). "A multi-prover interactive proof for NEXP sound against entangled provers".
107:
185:
is the length in bits of the description of a problem instance. Note further that the verification algorithm is
417:
197:
An alternative formulation of the PCP theorem states that the maximum fraction of satisfiable constraints of a
73:
979:
Anshu, Anurag; Breuckmann, Nikolas P.; Nirkhe, Chinmay (2023). "NLTS Hamiltonians from Good
Quantum Codes".
308:
111:
123:
115:
1240:
538:
296:) constraints. The other characterisation of the PCP theorem then guarantees the promise condition with
910:
96:
69:
834:
643:
1181:; Lund, Carsten (1990), "Nondeterministic exponential time has two-prover interactive protocols",
635:
1260:
1220:
1128:
1070:
1012:
984:
936:
900:
805:
639:
65:
1174:
1140:
1279:
1186:
1160:
1002:
926:
744:
697:
691:
670:
664:
1269:
1236:
1212:
1118:
1062:
994:
918:
815:
530:
312:
57:
50:
17:
1252:
510:) to yield a proof of the PCP theorem by Arora, Lund, Motwani, Sudan, and Szegedy in 1998 (
631:
316:
217:
143:
54:
914:
165:
of a solution can be given, such that the proof can be checked in polynomial time using
1042:
582:
569:
565:
542:
518:
127:
718:
1294:
1248:
1183:
SFCS '90: Proceedings of the 31st Annual
Symposium on Foundations of Computer Science
1178:
1157:
STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of computing
1152:
1144:
1102:
1082:
1050:
1034:
1016:
554:
522:
499:
1224:
954:
940:
506:), Feige, Goldwasser, Lund, Safra, and Szegedy (1991), and Arora and Safra in 1992 (
280:
Boolean variables on those bits of the proof. Since the verification algorithm uses
1244:
1148:
1106:
1086:
1074:
1038:
546:
534:
119:
1132:
76:
and logarithmic randomness complexity (uses a logarithmic number of random bits).
738:
1232:
1046:
550:
526:
272:
mentioned above can be seen by noticing that checking a constant number of bits
130:
as "a culmination of a sequence of impressive works rich in innovative ideas".
768:
1200:
606:
is a complexity class of multi-prover quantum interactive proofs systems with
561:
253:= {Φ: every assignment satisfies fewer than an α fraction of Φ's constraints},
1283:
835:"MIT News Release: 10-year-old problem in theoretical computer science falls"
557:
for work on the PCP theorem and its connection to hardness of approximation.
288:) bits of randomness, it can be represented as a CSP as described above with
1216:
1091:
In
Proceedings of the 33rd IEEE Symposium on Foundations on Computer Science
998:
922:
1274:
1123:
1109:(1998), "Probabilistic checking of proofs: A new characterization of NP",
1066:
1053:(1998), "Proof verification and the hardness of approximation problems",
897:
2018 IEEE 59th Annual
Symposium on Foundations of Computer Science (FOCS)
819:
743:. Texts in Computer Science. London: Springer-Verlag. pp. 119–127.
471:
The name of this theorem (the "PCP theorem") probably comes either from
202:
498:
Subsequently, the methods used in this work were extended by Babai,
110:, which investigates the inherent difficulty in designing efficient
989:
981:
Proceedings of the 55th Annual ACM Symposium on Theory of
Computing
905:
564:
discovered a significantly simpler proof of the PCP theorem, using
810:
106:
The PCP theorem is the cornerstone of the theory of computational
422:
666:
Complexity Theory: Exploring the Limits of Efficient Algorithms
1253:"Interactive proofs and the hardness of approximating cliques"
625:
591:
860:
858:
416:
The PCP theorem is the culmination of a long line of work on
867:"10-year-old problem in theoretical computer science falls"
244:= {Φ: all constraints in Φ are simultaneously satisfiable}
1155:(1991), "Checking computations in polylogarithmic time",
122:
as "the most important result in complexity theory since
503:
399:{\displaystyle {\mathsf {NP}}\subseteq {\mathsf {PCP}}}
79:
The PCP theorem says that for some universal constant
511:
347:
276:
in a proof can be seen as evaluating a constraint in
95:) that is formally verifiable with 99% accuracy by a
91:
can be rewritten as a different proof of length poly(
479:", or from the notation mentioned above (or both).
87:, any mathematical proof for a statement of length
693:Computational Complexity: A Conceptual Perspective
398:
795:
793:
408:is given in one of the lectures of Dexter Kozen.
1203:(2007), "The PCP theorem by gap amplification",
431:
1089:(1992), "Approximating clique is NP-complete",
628:-hard, implies the games quantum PCP theorem.
8:
959:Simons Institute for the Theory of Computing
771:. The authoritative version of the paper is
205:to approximate within some constant factor.
1306:Theorems in computational complexity theory
804:. IEEE Computer Society. pp. 243–252.
720:Computational Complexity: a Modern Approach
696:. Cambridge University Press. p. 405.
261:(CSP) over a Boolean alphabet with at most
507:
319:cannot be approximated efficiently unless
27:Theorem in computational complexity theory
1273:
1185:, IEEE Computer Society, pp. 16–25,
1122:
988:
904:
809:
381:
362:
361:
349:
348:
346:
655:
331:for NP with some additional structure.
369:
366:
363:
353:
350:
772:
161:is the class of problems for which a
7:
726:(Draft). Cambridge University Press.
717:Arora, Sanjeev; Barak, Boaz (2009).
173:) bits of randomness and by reading
329:probabilistically checkable proofs
234:) is an NP-hard decision problem:
62:probabilistically checkable proofs
25:
477:probabilistically checkable proof
466:probabilistically checkable proof
193:PCP and hardness of approximation
163:probabilistically checkable proof
432:Babai, Fortnow & Lund (1990)
873:from the original on 2012-08-01
841:from the original on 2014-02-02
259:constraint satisfaction problem
199:constraint satisfaction problem
39:computational complexity theory
865:Hardesty, Larry (2012-07-31).
833:Hardesty, Larry (2012-07-30).
502:, Levin, and Szegedy in 1991 (
393:
374:
305:boolean formula satisfiability
1:
208:Formally, for some constants
339:A proof of a weaker result,
268:The connection to the class
138:The PCP theorem states that
47:PCP characterization theorem
18:PCP Characterization Theorem
118:. It has been described by
32:Post correspondence problem
1327:
1311:Quantum information theory
265:variables per constraint.
29:
737:Kozen, Dexter C. (2006).
669:. Springer. p. 161.
108:hardness of approximation
68:that can be checked by a
955:"On the NLTS Conjecture"
568:. She received the 2019
112:approximation algorithms
30:Not to be confused with
1217:10.1145/1236457.1236459
1159:, ACM, pp. 21–32,
999:10.1145/3564246.3585114
923:10.1109/FOCS.2018.00075
787:, retrieved 2019-09-11.
763:See the 2005 preprint,
690:Oded Goldreich (2008).
313:shortest vector problem
309:maximum independent set
103:letters of that proof.
983:. pp. 1090–1096.
785:EATSC 2019 Gödel Prize
508:Arora & Safra 1992
438:Origin of the initials
400:
216:< 1, the following
1301:Randomized algorithms
1275:10.1145/226643.226652
1124:10.1145/273865.273901
1067:10.1145/278298.278306
740:Theory of Computation
663:Ingo Wegener (2005).
401:
116:optimization problems
899:. pp. 731–742.
820:10.1109/FOCS.2012.11
345:
97:randomized algorithm
70:randomized algorithm
49:) states that every
1268:(2), ACM: 268–292,
915:2018arXiv180103821N
869:. MIT News Office.
837:. MIT News Office.
311:in graphs, and the
99:that inspects only
45:(also known as the
1261:Journal of the ACM
1205:Journal of the ACM
1111:Journal of the ACM
1055:Journal of the ACM
640:Nikolas Breuckmann
418:interactive proofs
396:
1237:Goldwasser, Shafi
1192:978-0-8186-2082-9
1166:978-0-89791-397-3
932:978-1-5386-4230-6
703:978-0-521-88473-0
676:978-3-540-21045-0
512:Arora et al. 1998
504:Babai et al. 1991
16:(Redirected from
1318:
1286:
1277:
1257:
1227:
1195:
1169:
1135:
1126:
1098:
1077:
1021:
1020:
992:
976:
970:
969:
967:
966:
951:
945:
944:
908:
892:
886:
885:
879:
878:
862:
853:
852:
847:
846:
830:
824:
823:
813:
797:
788:
782:
776:
761:
755:
754:
734:
728:
727:
725:
714:
708:
707:
687:
681:
680:
660:
623:
605:
604:
599:
598:
594:
531:Shafi Goldwasser
495:
494:
490:
464:is explained at
407:
405:
403:
402:
397:
386:
385:
373:
372:
357:
356:
134:Formal statement
74:query complexity
58:complexity class
51:decision problem
21:
1326:
1325:
1321:
1320:
1319:
1317:
1316:
1315:
1291:
1290:
1255:
1231:
1199:
1193:
1173:
1167:
1139:
1101:
1081:
1043:Motwani, Rajeev
1033:
1030:
1025:
1024:
1009:
978:
977:
973:
964:
962:
953:
952:
948:
933:
894:
893:
889:
876:
874:
864:
863:
856:
844:
842:
832:
831:
827:
799:
798:
791:
783:
779:
762:
758:
751:
736:
735:
731:
723:
716:
715:
711:
704:
689:
688:
684:
677:
662:
661:
657:
652:
632:NLTS conjecture
615:
602:
601:
596:
590:
589:
578:
566:expander graphs
521:was awarded to
496:
492:
488:
486:
485:
463:
440:
414:
377:
343:
342:
340:
337:
252:
243:
233:
226:
218:promise problem
195:
136:
35:
28:
23:
22:
15:
12:
11:
5:
1324:
1322:
1314:
1313:
1308:
1303:
1293:
1292:
1289:
1288:
1249:Szegedy, Mario
1241:Lovász, László
1229:
1197:
1191:
1179:Fortnow, Lance
1171:
1165:
1153:Szegedy, Mario
1145:Fortnow, Lance
1137:
1103:Arora, Sanjeev
1099:
1083:Arora, Sanjeev
1079:
1061:(3): 501–555,
1051:Szegedy, Mario
1035:Arora, Sanjeev
1029:
1026:
1023:
1022:
1007:
971:
946:
931:
887:
854:
825:
789:
777:
756:
749:
729:
709:
702:
682:
675:
654:
653:
651:
648:
644:Chinmay Nirkhe
583:Dorit Aharonov
577:
576:Quantum analog
574:
543:Rajeev Motwani
484:
483:First theorem
481:
446:
439:
436:
413:
410:
395:
392:
389:
384:
380:
376:
371:
368:
365:
360:
355:
352:
336:
333:
255:
254:
250:
245:
241:
231:
224:
194:
191:
155:
154:
135:
132:
128:Oded Goldreich
124:Cook's theorem
72:) of constant
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1323:
1312:
1309:
1307:
1304:
1302:
1299:
1298:
1296:
1285:
1281:
1276:
1271:
1267:
1263:
1262:
1254:
1250:
1246:
1245:Safra, Shmuel
1242:
1238:
1234:
1230:
1226:
1222:
1218:
1214:
1210:
1206:
1202:
1198:
1194:
1188:
1184:
1180:
1176:
1175:Babai, László
1172:
1168:
1162:
1158:
1154:
1150:
1149:Levin, Leonid
1146:
1142:
1141:Babai, László
1138:
1134:
1130:
1125:
1120:
1117:(1): 70–122,
1116:
1112:
1108:
1107:Safra, Shmuel
1104:
1100:
1096:
1092:
1088:
1087:Safra, Shmuel
1084:
1080:
1076:
1072:
1068:
1064:
1060:
1056:
1052:
1048:
1044:
1040:
1039:Lund, Carsten
1036:
1032:
1031:
1027:
1018:
1014:
1010:
1008:9781450399135
1004:
1000:
996:
991:
986:
982:
975:
972:
960:
956:
950:
947:
942:
938:
934:
928:
924:
920:
916:
912:
907:
902:
898:
891:
888:
884:
872:
868:
861:
859:
855:
851:
840:
836:
829:
826:
821:
817:
812:
807:
803:
796:
794:
790:
786:
781:
778:
774:
770:
766:
760:
757:
752:
750:9781846282973
746:
742:
741:
733:
730:
722:
721:
713:
710:
705:
699:
695:
694:
686:
683:
678:
672:
668:
667:
659:
656:
649:
647:
645:
641:
637:
633:
629:
627:
622:
618:
613:
609:
593:
586:
584:
575:
573:
571:
567:
563:
558:
556:
555:Mario Szegedy
552:
548:
544:
540:
539:László Lovász
536:
532:
528:
524:
523:Sanjeev Arora
520:
515:
513:
509:
505:
501:
500:Lance Fortnow
491:
482:
480:
478:
474:
469:
467:
461:
457:
453:
449:
445:
442:The notation
437:
435:
433:
429:
425:
424:
419:
411:
409:
390:
387:
382:
378:
358:
334:
332:
330:
326:
322:
318:
314:
310:
306:
301:
299:
295:
291:
287:
283:
279:
275:
271:
266:
264:
260:
257:where Φ is a
249:
246:
240:
237:
236:
235:
230:
223:
219:
215:
211:
206:
204:
200:
192:
190:
188:
184:
180:
176:
172:
168:
164:
160:
152:
151:
146:
145:
141:
140:
139:
133:
131:
129:
125:
121:
117:
113:
109:
104:
102:
98:
94:
90:
86:
82:
77:
75:
71:
67:
63:
59:
56:
52:
48:
44:
40:
33:
19:
1265:
1259:
1233:Feige, Uriel
1211:(3): 12–es,
1208:
1204:
1182:
1156:
1114:
1110:
1094:
1090:
1058:
1054:
1047:Sudan, Madhu
980:
974:
963:. Retrieved
961:. 2021-06-30
958:
949:
896:
890:
881:
875:. Retrieved
849:
843:. Retrieved
828:
801:
780:
773:Dinur (2007)
759:
739:
732:
719:
712:
692:
685:
665:
658:
636:Anurag Anshu
630:
620:
616:
611:
607:
587:
579:
559:
547:Shmuel Safra
535:Carsten Lund
516:
497:
472:
470:
459:
455:
451:
447:
443:
441:
430:, proved by
427:
421:
415:
338:
324:
320:
302:
297:
293:
289:
285:
281:
277:
273:
269:
267:
262:
256:
247:
238:
228:
221:
213:
209:
207:
196:
187:non-adaptive
186:
182:
178:
174:
170:
166:
158:
156:
148:
142:
137:
120:Ingo Wegener
114:for various
105:
100:
92:
88:
84:
83:, for every
80:
78:
46:
42:
36:
1201:Dinur, Irit
572:for this.
570:Gödel Prize
551:Madhu Sudan
527:Uriel Feige
519:Gödel Prize
43:PCP theorem
1295:Categories
1028:References
990:2206.13228
965:2022-08-08
906:1801.03821
877:2012-08-10
845:2012-08-10
562:Irit Dinur
284:(log
1284:0004-5411
1097:(1): 2–13
1017:250072529
811:1207.0550
517:The 2001
475:meaning "
359:⊆
126:" and by
1251:(1996),
1225:53244523
941:53062680
871:Archived
839:Archived
769:TR05-046
600:, where
560:In 2005
454:),
317:lattices
1075:8561542
911:Bibcode
412:History
406:
341:
203:NP-hard
53:in the
1282:
1223:
1189:
1163:
1133:751563
1131:
1073:
1015:
1005:
939:
929:
767:
747:
700:
673:
642:, and
553:, and
487:": -->
157:where
66:proofs
41:, the
1256:(PDF)
1221:S2CID
1129:S2CID
1071:S2CID
1013:S2CID
985:arXiv
937:S2CID
901:arXiv
806:arXiv
724:(PDF)
650:Notes
473:"PCP"
335:Proof
1280:ISSN
1187:ISBN
1161:ISBN
1003:ISBN
927:ISBN
765:ECCC
745:ISBN
698:ISBN
671:ISBN
489:edit
423:NEXP
315:for
290:poly
212:and
60:has
1270:doi
1213:doi
1119:doi
1063:doi
995:doi
919:doi
816:doi
626:QMA
624:is
603:MIP
597:MIP
592:QMA
514:).
444:PCP
428:PCP
270:PCP
242:yes
225:yes
201:is
159:PCP
150:PCP
37:In
1297::
1278:,
1266:43
1264:,
1258:,
1247:;
1243:;
1239:;
1235:;
1219:,
1209:54
1207:,
1177:;
1151:;
1147:;
1143:;
1127:,
1115:45
1113:,
1105:;
1095:41
1093:,
1085:;
1069:,
1059:45
1057:,
1049:;
1045:;
1041:;
1037:;
1011:.
1001:.
993:.
957:.
935:.
925:.
917:.
909:.
880:.
857:^
848:.
814:.
792:^
646:.
638:,
619:−
595:⊆
549:,
545:,
541:,
537:,
533:,
529:,
525:,
434:.
426:⊆
325:NP
323:=
307:,
251:no
232:no
227:,
147:=
144:NP
55:NP
1287:.
1272::
1228:.
1215::
1196:.
1170:.
1136:.
1121::
1078:.
1065::
1019:.
997::
987::
968:.
943:.
921::
913::
903::
822:.
818::
808::
775:.
753:.
706:.
679:.
621:s
617:c
612:n
610:(
608:f
493:]
462:)
460:n
458:(
456:s
452:n
450:(
448:c
394:]
391:1
388:,
383:3
379:n
375:[
370:P
367:C
364:P
354:P
351:N
321:P
298:α
294:n
292:(
286:n
282:O
278:q
274:q
263:q
248:L
239:L
229:L
222:L
220:(
214:α
210:q
183:n
179:n
177:(
175:q
171:n
169:(
167:r
153:,
101:K
93:n
89:n
85:n
81:K
64:(
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.