zbMATH — the first resource for mathematics

Complexity issues in axiomatic extensions of Łukasiewicz logic. (English) Zbl 1165.03009
The present paper is devoted to the computational complexity of (consistent) axiomatic extensions of Łukasiewicz logic. it is proved that the set of tautologies of every axiomatic extension of propositional Łukasiewicz logic is coNP-complete. This is an extension of the present reviewer’s result to the effect that the tautology problem for Łukasiewicz infinite-valued propositional logic is coNP-complete [Theor. Comput. Sci. 52, 145–153 (1987; Zbl 0639.03042)]. Concerning Łukasiewicz predicate logics, one must distinguish between the case when truth-valuations take their values in the standard MV-algebra \([0,1]\) and the case when all MV-algebras are used to evaluate formulas. For this latter semantics it is proved that the set of tautologies in every axiomatic extension is \(\Sigma_1\)-complete. On the other hand, for \([0,1]\)-valued semantics, some axiomatic extensions have a \(\Pi_2\)-complete and others have a \(\Sigma_1\)-complete tautology problem.

03B50 Many-valued logic
03D15 Complexity of computation (including implicit computational complexity)
06D35 MV-algebras
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI