A. P. Kopylov.
On NP-completeness in Linear Logic.
Annals of Pure and Applied Logic 75 (1995) 179-213.
Abstract.
Linear Logic was introduced by Girard. In the current paper we consider multiplicative fragments of Linear Logic. We also consider the multiplicative fragment of Affine Logic, i.e., Linear Logic with weakening rule. These fragments are known to be NP-complete. In the current paper we establish exact bound of NP-completeness for the multiplicative fragments of Linear and Affine Logic.