Constant-only multiplicative linear logic is NP-complete (Q1342254)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Constant-only multiplicative linear logic is NP-complete |
scientific article |
Statements
Constant-only multiplicative linear logic is NP-complete (English)
0 references
28 November 1995
0 references
The paper considers the decision problem for the multiplicative fragment of linear logic without quantifiers or propositions: the constant only case. The authors show that this fragment is NP-complete. Three independent logics are considered: full propositional linear logic, restricted to multiplicative connectives and constants, and the constant only fragment. These calculi are considered as Gentzen-style sequent calculi since 3-Partition and 432-Partition are equivalent problems, so the authors encode an NP-complete problem, 432-Partition in the constant only fragment of linear logic restricted to multiplicative connectives and constants, and show this encoding is sound and complete. The decision problem for constant-only multiplicative linear logic is NP-complete. The complexity of most of the larger fragments of linear logic has already been completely characterized by P. Lincoln, J. Mitchell, A. Scedrov and N. Shankar.
0 references
NP-completeness
0 references
decision problem
0 references
multiplicative fragment of linear logic
0 references