Linear Logic Proof Games and Optimization

DOI10.2307/420993zbMATH Open0862.03023OpenAlexW2146375788MaRDI QIDQ5689264FDOQ5689264

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Decision problems for propositional linear logic
• Linear logic
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The Knowledge Complexity of Interactive Proof Systems
• Algebraic methods for interactive proof systems
• IP = PSPACE
• A game semantics for linear logic

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)