Linear Logic Proof Games and Optimization

DOI10.2307/420993MaRDI QIDQ5689264zbMATH OpenOpenAlexFDO

Authors John Mitchell, P. Lincoln, Andre Scedrov

Publication date 25 May 1997

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/e235e2c8617c2e769fee7675788acafc7c4e6985, http://www.math.ucla.edu/~asl/bsl/0203-toc.htm

zbMATH Keywords

non-approximabilityinteractive proofsPSPACE-hardnesscomplexity of determining winning strategieslinear logic gamesprobabilistic proof gameprobabilistic verifier characterization of PSPACErandomized proof checking

Mathematics Subject Classification ID

Applications of game theory (91A80) Automata and formal grammars in connection with logical questions (03D05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Optimization complexity of linear logic proof games
• scientific article; zbMATH DE number 786491
• scientific article; zbMATH DE number 1231522
• Games and full completeness for multiplicative linear logic

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• A game semantics for linear logic
• Algebraic methods for interactive proof systems
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Decision problems for propositional linear logic
• IP = PSPACE
• Linear logic
• The Knowledge Complexity of Interactive Proof Systems

Cited in

(2)

• A parallel game semantics for linear logic
• Proof-search in type-theoretic languages: An introduction

This page was built for publication: Linear Logic Proof Games and Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5689264)