𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Optimization complexity of linear logic proof games

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

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
218 KB
Volume
227
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

A class of linear logic proof games is developed, each with a numeric score that depends on the number of preferred axioms used in a complete or partial proof tree. The complexity of these games is analyzed for the NP-complete multiplicative fragment (MLL) extended with additive constants and the PSPACE-complete multiplicative, additive fragment (MALL) of propositional linear logic. In each case, it is shown that it is as hard to compute an approximation of the best possible score as it is to determine the optimal strategy. Furthermore, it is shown that no e cient heuristics exist unless there is an unexpected collapse in the complexity hierarchy.

πŸ“œ SIMILAR VOLUMES

The Complexity of Local Proof Search in
The Complexity of Local Proof Search in Linear Logic: (Extended Abstract)
✍ Patrick D. Lincoln; John C. Mitchell; Andre Scedrov πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 473 KB

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,

The complexity of the temporal logic wit
The complexity of the temporal logic with β€œuntil” over general linear time
✍ M. Reynolds πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 350 KB

It is shown that the decision problem for the temporal logic with the strict until operator over general linear time is PSPACE-complete. This shows that it is no harder to reason with arbitrary linear orderings than with discrete linear time temporal logics. New techniques are used to give a PSPACE