84:
74:
53:
707:
all, and that may require a very long search. If the proof does not exist, a search for it may never end. We assume the prover is all-powerful in the sense that it is able to find a message that achieves the goal if such a message exists, and is able to avoid being stuck in an infinite search if the proof does not exist. In other words, we are not really concerned about how the prover works. We are studying the verifier.
256:
179:
158:
22:
587:
527:
500:
646:
traditional machines. They've also been valuable in proving other things like the lower bounds on approximation algorithms. This stuff should be covered in any second-semester course on complexity, at least in passing. I provided 10 references, most of which have received many hundreds of citations and are seminal works. Some you can read for free, have a look.
726:
The current article says, "Although NP may be viewed as using interaction, it wasn't until 1985 that the concept of computation through interaction was conceived by two independent groups of researchers." It is well known that
Goldwasser-Micali-Rackoff existed by the middle of 1983; for instance, I
706:
In the abstract machine of an interactive proof, the prover is trying to convince the verifier about a statement, and the question is if there are messages that the prover can supply to the verifier to convince it. In order to give a proof of anything, the proof must be found, provided it exists at
645:
It's responsible for at least two of the most important theorems in complexity theory, the IP=PSPACE theorem and the PCP Theorem. Both of these are widely cited and held in high regard because of their difficulty, how surprising they are, and how they link interactive proof systems together with
277:
727:
heard their work expounded during lunches at the FCT'83 conference in late August in
Borgholm, Sweden. It was rejected from three previous STOC/FOCS'es. Not sure how to revise the article, so I'll leave it as a discussion point.
577:
673:
My written english is not so well, but there is no Entry in German for this one, so I strived through the english version. You should
Include a remarkt that class IP and PSPACE are equivalent!
301:
140:
703:
Real machines can only produce text by following mechanical procedures, possibly involving random choices from finite sets, and otherwise relying on given inputs and built-in constants.
441:
358:
296:
626:
Could we have full references for the papers you mention, so I can check where else they have been cited? Has the concept been used to prove anything else of interest? --
785:
601:
765:
229:
219:
623:
Hmmm. I'm certainly not an expert in computational complexity theory, but I'm unfamiliar with this idea, and the article at the moment sounds overly enthusiastic.
780:
770:
760:
567:
195:
790:
775:
755:
403:
130:
750:
543:
377:
596:
510:
242:
186:
163:
106:
466:
349:
534:
505:
330:
97:
58:
422:
681:
I admit I know nothing about the subject of the article, but I think there may be a tad too many boldings in this article.--
387:
268:
33:
397:
311:
700:
The lead does not give enough context. Only after reading on I infer the following context, but I am not an expert.
432:
194:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
459:
21:
368:
39:
83:
542:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
712:
686:
635:
627:
89:
634:
OK, it's real, and there are papers in the area. Still not sure how important it is, though. --
73:
52:
732:
659:
287:
339:
191:
663:
413:
255:
278:
Requested articles/Applied arts and sciences/Computer science, computing, and
Internet
744:
708:
682:
647:
736:
716:
690:
650:
728:
539:
667:
102:
79:
320:
586:
178:
157:
526:
499:
666:
and they get cited a lot (hundreds of citations for each of them).
396:
Find pictures for the biographies of computer scientists (see
15:
585:
658:
If that still matters, it's a fairly popular concept in
538:, a collaborative effort to improve the coverage of
190:, a collaborative effort to improve the coverage of
101:, a collaborative effort to improve the coverage of
662:. You can look the references up in, for example,
302:Computer science articles needing expert attention
442:WikiProject Computer science/Unreferenced BLPs
8:
359:Computer science articles without infoboxes
297:Computer science articles needing attention
19:
494:
263:Here are some tasks awaiting attention:
237:
152:
47:
786:High-importance Computer science articles
766:Mid-importance Computer science articles
496:
154:
49:
204:Knowledge:WikiProject Computer science
781:High-importance Cryptography articles
771:WikiProject Computer science articles
761:Start-Class Computer science articles
207:Template:WikiProject Computer science
7:
532:This article is within the scope of
184:This article is within the scope of
95:This article is within the scope of
38:It is of interest to the following
552:Knowledge:WikiProject Cryptography
378:Timeline of computing 2020–present
14:
791:WikiProject Cryptography articles
776:Start-Class Cryptography articles
756:Mid-priority mathematics articles
555:Template:WikiProject Cryptography
404:Computing articles needing images
115:Knowledge:WikiProject Mathematics
751:Start-Class mathematics articles
525:
498:
254:
177:
156:
118:Template:WikiProject Mathematics
82:
72:
51:
20:
572:This article has been rated as
224:This article has been rated as
135:This article has been rated as
696:The lead forgets to explain...
1:
594:This article is supported by
546:and see a list of open tasks.
458:Tag all relevant articles in
198:and see a list of open tasks.
109:and see a list of open tasks.
597:WikiProject Computer science
467:WikiProject Computer science
243:WikiProject Computer science
187:WikiProject Computer science
398:List of computer scientists
807:
717:07:32, 22 April 2010 (UTC)
670:20:49, May 19, 2004 (UTC)
230:project's importance scale
737:02:29, 23 June 2011 (UTC)
691:10:15, 26 July 2008 (UTC)
630:04:58, 30 Jul 2003 (UTC)
593:
571:
520:
460:Category:Computer science
236:
223:
210:Computer science articles
172:
134:
67:
46:
677:Bolding of abbreviations
651:09:26, 27 May 2005 (UTC)
638:05:02, 30 Jul 2003 (UTC)
535:WikiProject Cryptography
462:and sub-categories with
141:project's priority scale
98:WikiProject Mathematics
590:
423:Computer science stubs
28:This article is rated
589:
558:Cryptography articles
241:Things you can help
121:mathematics articles
591:
90:Mathematics portal
34:content assessment
660:complexity theory
616:
615:
612:
611:
608:
607:
493:
492:
489:
488:
485:
484:
481:
480:
151:
150:
147:
146:
798:
578:importance scale
560:
559:
556:
553:
550:
529:
522:
521:
516:
513:
511:Computer science
502:
495:
471:
465:
340:Computer science
269:Article requests
258:
251:
250:
238:
212:
211:
208:
205:
202:
201:Computer science
192:Computer science
181:
174:
173:
168:
164:Computer science
160:
153:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
806:
805:
801:
800:
799:
797:
796:
795:
741:
740:
724:
698:
679:
621:
602:High-importance
574:High-importance
557:
554:
551:
548:
547:
515:High‑importance
514:
508:
477:
474:
469:
463:
451:Project-related
446:
427:
408:
382:
363:
344:
325:
306:
282:
209:
206:
203:
200:
199:
166:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
804:
802:
794:
793:
788:
783:
778:
773:
768:
763:
758:
753:
743:
742:
723:
720:
697:
694:
678:
675:
656:
655:
654:
653:
640:
639:
620:
617:
614:
613:
610:
609:
606:
605:
592:
582:
581:
570:
564:
563:
561:
544:the discussion
530:
518:
517:
503:
491:
490:
487:
486:
483:
482:
479:
478:
476:
475:
473:
472:
455:
447:
445:
444:
438:
428:
426:
425:
419:
409:
407:
406:
401:
393:
383:
381:
380:
374:
364:
362:
361:
355:
345:
343:
342:
336:
326:
324:
323:
317:
307:
305:
304:
299:
293:
283:
281:
280:
274:
262:
260:
259:
247:
246:
234:
233:
226:Mid-importance
222:
216:
215:
213:
196:the discussion
182:
170:
169:
167:Mid‑importance
161:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
803:
792:
789:
787:
784:
782:
779:
777:
774:
772:
769:
767:
764:
762:
759:
757:
754:
752:
749:
748:
746:
739:
738:
734:
730:
721:
719:
718:
714:
710:
704:
701:
695:
693:
692:
688:
684:
676:
674:
671:
669:
665:
661:
652:
649:
644:
643:
642:
641:
637:
636:Robert Merkel
633:
632:
631:
629:
628:Robert Merkel
624:
618:
603:
600:(assessed as
599:
598:
588:
584:
583:
579:
575:
569:
566:
565:
562:
545:
541:
537:
536:
531:
528:
524:
523:
519:
512:
507:
504:
501:
497:
468:
461:
457:
456:
454:
452:
448:
443:
440:
439:
437:
435:
434:
429:
424:
421:
420:
418:
416:
415:
410:
405:
402:
399:
395:
394:
392:
390:
389:
384:
379:
376:
375:
373:
371:
370:
365:
360:
357:
356:
354:
352:
351:
346:
341:
338:
337:
335:
333:
332:
327:
322:
319:
318:
316:
314:
313:
308:
303:
300:
298:
295:
294:
292:
290:
289:
284:
279:
276:
275:
273:
271:
270:
265:
264:
261:
257:
253:
252:
249:
248:
244:
240:
239:
235:
231:
227:
221:
218:
217:
214:
197:
193:
189:
188:
183:
180:
176:
175:
171:
165:
162:
159:
155:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
725:
705:
702:
699:
680:
672:
657:
625:
622:
595:
573:
549:Cryptography
540:Cryptography
533:
506:Cryptography
450:
449:
433:Unreferenced
431:
430:
412:
411:
386:
385:
367:
366:
348:
347:
329:
328:
310:
309:
286:
285:
267:
266:
225:
185:
137:Mid-priority
136:
96:
62:Mid‑priority
40:WikiProjects
722:Origin year
664:this survey
112:Mathematics
103:mathematics
59:Mathematics
30:Start-class
745:Categories
321:Computing
709:Cacadril
683:Rockfang
619:Untitled
369:Maintain
312:Copyedit
729:KWRegan
576:on the
350:Infobox
288:Cleanup
228:on the
139:on the
668:Andris
331:Expand
36:scale.
414:Stubs
388:Photo
245:with:
733:talk
713:talk
687:talk
648:Deco
568:High
220:Mid
131:Mid
747::
735:)
715:)
689:)
604:).
509::
470:}}
464:{{
731:(
711:(
685:(
580:.
453::
436::
417::
400:)
391::
372::
353::
334::
315::
291::
272::
232:.
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
