Linear Logic Proof Games and Optimization

DOI10.2307/420993zbMath0862.03023OpenAlexW2146375788MaRDI QIDQ5689264

John C. Mitchell, Andrej Scedrov, Patrick D. Lincoln

Publication date: 25 May 1997

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

Full work available at URL: https://semanticscholar.org/paper/e235e2c8617c2e769fee7675788acafc7c4e6985

zbMATH Keywords

interactive proofsnon-approximabilityPSPACE-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 of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items

Proof-search in type-theoretic languages: An introduction

Cites Work

• Unnamed Item
• Unnamed Item
• Linear logic
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• A game semantics for linear logic
• Decision problems for propositional linear logic
• The Knowledge Complexity of Interactive Proof Systems
• Algebraic methods for interactive proof systems
• IP = PSPACE