Constant-only multiplicative linear logic is NP-complete

DOI10.1016/0304-3975(94)00108-1zbMath0826.03002OpenAlexW2021005328WikidataQ56340933 ScholiaQ56340933MaRDI QIDQ1342254

Timothy Winkler, Patrick D. Lincoln

Publication date: 28 November 1995

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00108-1

zbMATH Keywords

NP-completenessdecision problemmultiplicative fragment of linear logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items

First-order linear logic without modalities is NEXPTIME-hard, Unnamed Item, System BV is NP-complete, Parsing MELL proof nets, The decidability of the intensional fragment of classical linear logic, ! and ? – Storage as tensorial strength

Uses Software

• Lolli

Cites Work

• Linear logic
• Computational interpretations of linear logic
• Decision problems for propositional linear logic
• Some Properties of Linear Logic Proved by Semantic Methods
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item