Computational complexities of axiomatic extensions of monoidal t-norm based logic

摘要

We study the computational complexity of some axiomatic extensions of the monoidal t-norm based logic (MTL), namely NM corresponding to the logic of the so-called nilpotent minimum t-norm (due to Fodor in Fuzzy Sets Syst 69:141–156, 1995); and SMTL corresponding to left-continuous strict t-norms, introduced by Esteva (and others) (Fuzzy Sets Syst 132(1):107–112, 2002; 136(3):263–282, 2003). In particular, we show that the sets of 1-satisfiable and positively satisfiable formulae of both NM and SMTL are NP-complete, while the set of 1-tautologies of NM and the set of positive tautologies of both NM and SMTL are co-NP-complete. The set of 1-tautologies of SMTL is only shown to be co-NP-hard, and it remains open if this set is in co-NP. Also, some results on the relations between these sets are obtained. We point out that results about 1-satisfiability and 1-tautology for NM are already well-known. However, in this paper, those results are proved in different ways.