The Complexity of Local Proof Search in Linear Logic: (Extended Abstract)

✍ Scribed by Patrick D. Lincoln; John C. Mitchell; Andre Scedrov

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 473 KB
• Volume: 3
• Category: Article
• ISSN: 1571-0661
• DOI: 10.1016/s1571-0661(05)80410-4

✦ Synopsis

Proof search in linear logic is known to be di cult: the provability of propositional linear logic formulas is undecidable. Even without the modalities, multiplicativeadditive fragment of propositional linear logic, mall, i s k n o wn to be pspace-complete, and the pure multiplicative fragment, mll, i s k n o wn to be np-complete. However, this still leaves open the possibility that there might be proof search heuristics (perhaps involving randomization) that often lead to a proof if there is one, or always lead to something close to a proof. One approach to these problems is to study strategies for proof games. A class of linear logic proof games is developed, each w i t h a n umeric score that depends on the number of certain preferred axioms used in a complete or partial proof tree. Using recent t e c hniques for proving lower bounds on optimization problems, the complexity of these games is analyzed for the fragment mll extended with additive constants and for the fragment mall. I t is shown that no e cient heuristics exist unless there is an unexpected collapse in the complexity hierarchy.