{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:14:36Z","timestamp":1761610476156,"version":"build-2065373602"},"reference-count":30,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2005,5,3]],"date-time":"2005-05-03T00:00:00Z","timestamp":1115078400000},"content-version":"vor","delay-in-days":3410,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Electronic Notes in Theoretical Computer Science"],"published-print":{"date-parts":[[1996]]},"DOI":"10.1016\/s1571-0661(05)80410-4","type":"journal-article","created":{"date-parts":[[2005,5,6]],"date-time":"2005-05-06T15:34:43Z","timestamp":1115393683000},"page":"120-129","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["The Complexity of Local Proof Search in Linear Logic"],"prefix":"10.1016","volume":"3","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":"78","reference":[{"key":"10.1016\/S1571-0661(05)80410-4_BIB1","doi-asserted-by":"crossref","first-page":"543","DOI":"10.2307\/2275407","article-title":"Games and full completeness for multiplicative linear logic","volume":"59","author":"Abramsky","year":"1994","journal-title":"Journal of Symbolic Logic"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB2","first-page":"1","article-title":"Full abstraction for PCF (Extended abstract)","author":"Abramsky","year":"1994","journal-title":"Proc. TACS '94, Springer LNCS Vol. 789"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB3","series-title":"Proc. 33-rd Annual IEEE Symposium on Foundations of Computer Science","first-page":"14","article-title":"Proof verification and hardness of approximation problems","author":"Arora","year":"1992"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB4","first-page":"2","article-title":"Probabilistic checking of proofs; A new characterization of NP","author":"Arora","year":"1992"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB5","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","article-title":"Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes","volume":"36","author":"Babai","year":"1988","journal-title":"J. Computer System Sciences"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB6","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0168-0072(92)90073-9","article-title":"A game semantics for linear logic","volume":"56","author":"Blass","year":"1992","journal-title":"Annals of Pure and Applied Logic"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB7","series-title":"Proc. 9-th Annual IEEE Conference on Structure in Complexity Theory","first-page":"280","article-title":"Random debaters and the hardness of approximating stochastic functions","author":"Condon","year":"1994"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB8","doi-asserted-by":"crossref","unstructured":"A. Condon, J. Feigenbaum, C. Lund, and P. Shor. Probabilistically checkable debate systems and nonapproximability of PSPACE-hard functions. Chicago Journal of Theoretical Computer Science, page http:\/\/www.cs.chicago.edu\/publications\/cjtcs\/articles\/1995\/4\/contents.html, 1995, No. 4. Extended abstract in Proc. 25-th ACM Symposium on Theory of Computing, pages 305-314, ACM, New York, 1993.","DOI":"10.1145\/167088.167190"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB9","series-title":"Proc. 11-th Annual IEEE Symposium on Logic in Computer Science, New Brunswick, NJ","article-title":"Game semantics and abstract machines","author":"Danos","year":"1996"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(87)90045-4","article-title":"Linear logic","volume":"50","author":"Girard","year":"1987","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB11","article-title":"Linear logic: its syntax and semantics","volume":"volume 222","author":"Girard","year":"1995"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB12","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","article-title":"The knowledge complexity of interactive proof systems","volume":"18","author":"Goldwasser","year":"1989","journal-title":"SIAM J. Computing"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB13","doi-asserted-by":"crossref","unstructured":"J. M. E. Hyland and C.-H. L. Ong. Pi-calculus, dialogue games and PCF. In Proceedings of the 7th ACM Conference on Functional Programming Languages and Computer Architecture, pages 96\u2013107. ACM Press, 1995.","DOI":"10.1145\/224164.224189"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB14","series-title":"Proc. 9-th Annual IEEE Conference on Structure in Complexity Theory","first-page":"356","article-title":"Generalized CNF satisfiability problems and non-efficient approximability","author":"Hunt III","year":"1994"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB15","unstructured":"A. Joyal. Free lattices, communication, and money games. In: Proceedings of the 10-th International Congress of Logic, Methodology, and Philosophy of Science, Firenze, 1995."},{"key":"10.1016\/S1571-0661(05)80410-4_BIB16","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0168-0072(94)90085-X","article-title":"The complexity of Horn fragments of linear logic","volume":"69","author":"Kanovich","year":"1994","journal-title":"Annals of Pure and Applied Logic"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB17","first-page":"464","article-title":"Games semantics for full propositional linear logic","author":"Lamarche","year":"1995","journal-title":"Proc. 10-th Annual IEEE Symposium on Logic in Computer Science, San Diego"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB18","doi-asserted-by":"crossref","unstructured":"P. Lincoln, J. Mitchell, A. Scedrov, and N. Shankar. Decision problems for propositional linear logic. Annals of Pure and Applied Logic, 56:239-311, 1992. Extended abstract in Proc. 31-st Annual IEEE Symposium on Foundations of Computer Science, pages 662-671, 1990.","DOI":"10.1109\/FSCS.1990.89588"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB19","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0304-3975(94)00108-1","article-title":"Constant-Only Multiplicative Linear Logic is NP-Complete","volume":"135","author":"Lincoln","year":"1994","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB20","first-page":"147","article-title":"Stochastic interaction and linear logic","volume":"Volume 222","author":"Lincoln","year":"1995"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB21","article-title":"Linear logic proof games and optimization","author":"Lincoln","year":"1996","journal-title":"Preliminary report"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB22","doi-asserted-by":"crossref","DOI":"10.2307\/420993","article-title":"Linear logic proof games and optimization. Extended abstract","author":"Lincoln","year":"1996","journal-title":"Bulletin of Symbolic Logic"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB23","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1145\/146585.146605","article-title":"Algebraic methods for interactive proof systems","volume":"39","author":"Lund","year":"1992","journal-title":"J. ACM"},{"year":"1995","series-title":"Randomized Algorithms","author":"Motwani","key":"10.1016\/S1571-0661(05)80410-4_BIB24"},{"year":"1994","series-title":"Computational Complexity","author":"Papadimitriou","key":"10.1016\/S1571-0661(05)80410-4_BIB25"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB26","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. In Proc. 20-th Annual ACM Symposium on Theory of Computing, pages 229-234, 1988. Also in J. Computer System Sciences, 1991.","DOI":"10.1145\/62212.62233"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB27","series-title":"Current Trends in Theoretical Computer Science","first-page":"377","article-title":"A brief guide to linear logic","author":"Scedrov","year":"1993"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB28","doi-asserted-by":"crossref","unstructured":"A. Scedrov. Linear Logic and Computation: A Survey. In H. Schwichtenberg, editor, Proof and Computation, Proceedings Marktoberdorf Summer School 1993, volume 139, pages 379-395. NATO Advanced Science Institutes, Series F, Springer-Verlag, Berlin, 1995.","DOI":"10.1007\/978-3-642-79361-5_9"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB29","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1145\/146585.146609","article-title":"IP = PSPACE","volume":"39","author":"Shamir","year":"1992","journal-title":"J. ACM"},{"key":"10.1016\/S1571-0661(05)80410-4_BIB30","series-title":"Proc. 8-th Annual IEEE Conference on Structure in Complexity Theory","first-page":"305","article-title":"NP-complete problems have a version that's hard to approximate","author":"Zuckerman","year":"1993"}],"container-title":["Electronic Notes in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066105804104?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066105804104?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:09:04Z","timestamp":1761610144000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571066105804104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"references-count":30,"alternative-id":["S1571066105804104"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0661(05)80410-4","relation":{},"ISSN":["1571-0661"],"issn-type":[{"type":"print","value":"1571-0661"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"The Complexity of Local Proof Search in Linear Logic","name":"articletitle","label":"Article Title"},{"value":"Electronic Notes in Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S1571-0661(05)80410-4","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1996 Elsevier B.V.","name":"copyright","label":"Copyright"}]}}