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
interactive proofsnon-approximabilityPSPACE-hardnesscomplexity of determining winning strategieslinear logic gamesprobabilistic proof gameprobabilistic verifier characterization of PSPACErandomized proof checking
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
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