Constant-only multiplicative linear logic is NP-complete
type: Item
instance of: scholarly article
title: Constant-only multiplicative linear logic is NP-complete
zbMATH Open document ID: 0826.03002
DOI: 10.1016/0304-3975(94)00108-1
author: Timothy Winkler
author: P. Lincoln
published in: Theoretical Computer Science
publication date: 1995-11-28T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03B20
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 710243
zbMATH Keywords: NP-completeness
zbMATH Keywords: decision problem
zbMATH Keywords: multiplicative fragment of linear logic
Wikidata QID: Q56340933
reviewed by: Andrzej Biela
describes a project that uses: Lolli
MaRDI profile type: Publication
full work available at URL: 0304-3975(94)00108-1
OpenAlex ID: W2021005328
cites work: Computational interpretations of linear logic
cites work: Some Properties of Linear Logic Proved by Semantic Methods
cites work: Q5620723
cites work: Q4198056
cites work: Linear logic
cites work: Q5813181
cites work: Decision problems for propositional linear logic
cites work: Q3827993
DBLP publication ID: journals/tcs/LincolnW94
description: scientific article; zbMATH DE number 710243