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

complexity of determining winning strategiesinteractive proofslinear logic gamesnon-approximabilityprobabilistic proof gameprobabilistic verifier characterization of PSPACEPSPACE-hardnessrandomized proof checking

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• IP = PSPACE
• Linear logic
• The Knowledge Complexity of Interactive Proof Systems

Cited in

(4)

• A parallel game semantics for linear logic
• Optimization complexity of linear logic proof games
• Proof-search in type-theoretic languages: An introduction
• scientific article; zbMATH DE number 1231522 (Why is no real title available?)

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)