{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:18Z","timestamp":1761611178574},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T00:00:00Z","timestamp":1389744000000},"content-version":"unspecified","delay-in-days":6345,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log."],"published-print":{"date-parts":[[1996,9]]},"abstract":"<jats:p><jats:bold>\u00a7 1. Introduction<\/jats:bold>. Perhaps the most surprising recent development in complexity theory is the discovery that the class NP can be characterized using a form of randomized proof checker that only examines a constant number of bits of the \u201cproof\u201d that a string is in a language [6, 5, 31, 3, 4]. More specifically, writing \u2223<jats:italic>x<\/jats:italic>\u2223 for the length of a string <jats:italic>x<\/jats:italic>, a language <jats:italic>L<\/jats:italic> in the class NP of languages recognizable in Nondeterministic polynomial time is traditionally given by a polynomial <jats:italic>p<\/jats:italic> and a polynomial-time predicate <jats:italic>P<\/jats:italic> such that a string <jats:italic>x<\/jats:italic> is in <jats:italic>L<\/jats:italic> iff there is some string <jats:italic>y<\/jats:italic> satisfying <jats:italic>P<\/jats:italic>(x, y), where \u2223<jats:italic>y<\/jats:italic>\u2223 \u2264 <jats:italic>p<\/jats:italic> (\u2223<jats:italic>x<\/jats:italic>\u2223). Intuitively, we can think of a string <jats:italic>y<\/jats:italic> as a possible proof that <jats:italic>x \u03f5 L<\/jats:italic>, with the predicate <jats:italic>P<\/jats:italic> some kind of proof checker that distinguishes good proofs from bad ones. A string <jats:italic>x<\/jats:italic> is therefore in a language <jats:italic>L<\/jats:italic> \u03f5 NP if there is a short proof that <jats:italic>x \u03f5 L<\/jats:italic>, and not in <jats:italic>L<\/jats:italic> otherwise. The surprising discovery is that the deterministic proof checker that reads the entire input and proof can be replaced by a probabilistic verifier that on input <jats:italic>x<\/jats:italic> and possible proof <jats:italic>y<\/jats:italic>, where <jats:italic>y<\/jats:italic> is presented in a certain way, flips at most <jats:italic>O<\/jats:italic> (log \u2223<jats:italic>x<\/jats:italic>\u2223) coins and reads at most a constant number of bits of <jats:italic>x<\/jats:italic> and <jats:italic>y<\/jats:italic>. Obviously, a probabilistic verifier that does not read the whole proof will sometimes make mistakes. However, the surprising and essentially non-intuitive mathematical fact is that for each language <jats:italic>L<\/jats:italic> in NP, it is possible to find a polynomial <jats:italic>q<\/jats:italic> and verifier <jats:italic>V<\/jats:italic> flipping a logarithmic number of coins and reading a constant number of bits such that, for any <jats:italic>x \u03f5 L<\/jats:italic>, there exists <jats:italic>y<\/jats:italic> with \u2223<jats:italic>y<\/jats:italic>\u2223 \u2264 q(\u2223<jats:italic>x<\/jats:italic>\u2223) and with <jats:italic>V (x, y)<\/jats:italic> accepting with probability 1 and, for <jats:italic>x \u2209 L<\/jats:italic>, there is no <jats:italic>y<\/jats:italic> with \u2223<jats:italic>y<\/jats:italic>\u2223 \u2264 <jats:italic>q<\/jats:italic>(\u2223<jats:italic>x<\/jats:italic>\u2223) and with <jats:italic>V (x, y)<\/jats:italic> accepting with probability \u2265 1\/4. This idea canalsobeextended to PSPACE [10, 9], using a game that alternates between two players instead of a proof presented by a \u201csingle player.\u201d<\/jats:p>","DOI":"10.2307\/420993","type":"journal-article","created":{"date-parts":[[2006,5,7]],"date-time":"2006-05-07T03:09:17Z","timestamp":1146971357000},"page":"322-338","source":"Crossref","is-referenced-by-count":3,"title":["Linear Logic Proof Games and Optimization"],"prefix":"10.1017","volume":"2","author":[{"given":"Patrick D.","family":"Lincoln","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John C.","family":"Mitchell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andre","family":"Scedrov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S1079898600007848_ref012","first-page":"2","volume-title":"Proceedings of the 32-nd Annual IEEE Symposium on Foundations of Computer Science","author":"Feige","year":"1991"},{"key":"S1079898600007848_ref015","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511629150"},{"key":"S1079898600007848_ref004","volume-title":"Approximation algorithms for NP-hardproblems","author":"Arora","year":"1996"},{"key":"S1079898600007848_ref021","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(92)90075-B"},{"key":"S1079898600007848_ref026","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"S1079898600007848_ref013","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"Garey","year":"1979"},{"key":"S1079898600007848_ref016","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"S1079898600007848_ref019","volume-title":"Proceedings of the 10-th international congress of logic, methodology, and philosophy of science, Firenze","author":"Joyal"},{"key":"S1079898600007848_ref017","first-page":"96","volume-title":"Proceedings of the 7th ACM Conference on Functional Programming Languages and Computer Architecture","author":"Hyland","year":"1995"},{"key":"S1079898600007848_ref002","first-page":"1","volume-title":"Proceedings of the TACS '94","volume":"789","author":"Abramsky","year":"1994"},{"key":"S1079898600007848_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90045-4"},{"key":"S1079898600007848_ref027","volume-title":"Computational complexity","author":"Papadimitriou","year":"1994"},{"key":"S1079898600007848_ref022","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511629150.008"},{"key":"S1079898600007848_ref001","unstructured":"[1] Abramsky S. and Jagadeesan R. , Games andfull completeness for multiplicative linear logic, this JOURNAL, vol. 59 (1994), pp. 543\u2013574."},{"key":"S1079898600007848_ref024","volume-title":"Proceedings linear logic '96, Tokyo meeting","author":"Lincoln","year":"1996"},{"key":"S1079898600007848_ref031","doi-asserted-by":"crossref","unstructured":"[31] Sudan M. , Efficient checking of polynomials and proofs and the hardness of approximation problems, ACM Distinguished Dissertation Series, Springer-Verlag, 1996, revised version of a Ph.D. Dissertation, University of California, Berkeley, 1993.","DOI":"10.1007\/3-540-60615-7"},{"key":"S1079898600007848_ref025","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"S1079898600007848_ref010","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.1995.004"},{"key":"S1079898600007848_ref030","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"S1079898600007848_ref029","first-page":"379","volume-title":"Proof and computation, proceedings Marktoberdorf summer school 1993","volume":"139","author":"Scedrov","year":"1995"},{"key":"S1079898600007848_ref011","volume-title":"Proceedings of the 11-th Annual IEEE Symposium on Logic in Computer Science, New Brunswick, NJ","author":"Danos","year":"1996"},{"key":"S1079898600007848_ref005","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267823"},{"key":"S1079898600007848_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(92)90073-9"},{"key":"S1079898600007848_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"S1079898600007848_ref006","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267824"},{"key":"S1079898600007848_ref003","unstructured":"[3] Arora S. , Probabilistic checking of proofs and hardness of approximation problems, Technical Report CS-TR-476-94, Department of Computer Science, Princeton University, 1994, revised version of a Ph.D. Dissertation, University of California, Berkeley, 1994."},{"key":"S1079898600007848_ref018","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1994.315789"},{"key":"S1079898600007848_ref020","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1995.523280"},{"key":"S1079898600007848_ref023","unstructured":"[23] Lincoln P. D. , Linear logic proof games and optimization, Preliminary report, 01 1996, available by anonymous ftp from ftp.cis.upenn.edu as pub\/papers\/scedrov\/approx.[dvi,ps].Z."},{"key":"S1079898600007848_ref028","doi-asserted-by":"publisher","DOI":"10.1142\/9789812794499_0027"},{"key":"S1079898600007848_ref009","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1994.315796"}],"container-title":["Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600007848","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T16:38:26Z","timestamp":1557679106000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600007848\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["S1079898600007848"],"URL":"https:\/\/doi.org\/10.2307\/420993","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}