Constant-only multiplicative linear logic is NP-complete

DOI10.1016/0304-3975(94)00108-1MaRDI QIDQ1342254zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Timothy Winkler, P. 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) Subsystems of classical logic (including intuitionistic logic) (03B20) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Decision problems for propositional linear logic
• scientific article; zbMATH DE number 785051
• Direct encodings of NP-complete problems into Horn sequents of multiplicative linear logic
• Multiplicative-additive proof equivalence is \textsf{logspace}-complete, via binary decision trees
• scientific article; zbMATH DE number 786489

Cites work

• scientific article; zbMATH DE number 4103051 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3344729 (Why is no real title available?)
• scientific article; zbMATH DE number 3074068 (Why is no real title available?)
• Computational interpretations of linear logic
• Decision problems for propositional linear logic
• Linear logic
• Some Properties of Linear Logic Proved by Semantic Methods

Cited in

(8)

• Decision problems for propositional linear logic
• System BV is NP-complete
• ! and ? – Storage as tensorial strength
• Proof diagrams for multiplicative linear logic
• Direct encodings of NP-complete problems into Horn sequents of multiplicative linear logic
• Parsing MELL proof nets
• First-order linear logic without modalities is NEXPTIME-hard
• The decidability of the intensional fragment of classical linear logic

Describes a project that uses

Uses Software

• Lolli

This page was built for publication: Constant-only multiplicative linear logic is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1342254)