Constant-only multiplicative linear logic is NP-complete
From MaRDI portal
Publication:1342254
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
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
Cites Work