Lewis dichotomies in many-valued logics (Q1935553)

In 1979, \textit{H. R. Lewis} [Math. Syst. Theory 13, 45--53 (1979; Zbl 0428.03035)] showed that the computational complexity of the Boolean satisfiability problem dichotomizes, depending on the Boolean operations available to formulate instances: intractable (NP-complete) if negation of implication is definable, and tractable (in P) otherwise. Recently, an investigation in the same spirit has been extended to nonclassical propositional logics, modal logics in particular, by \textit{M. Bauland} et al. in [Lect. Notes Comput. Sci. 3884, 500--511 (2006; Zbl 1136.68408); Log. Methods Comput. Sci. 5, No. 1, Paper 1, 21 p. (2009; Zbl 1183.03017)]. In the current paper, the author pursues this line in the realm of many-valued propositional logics, and obtains complexity classifications for the parameterized satisfiability problem of two pertinent samples, Kleene and Gödel logics. Widening the dichotomy by Lewis on Boolean operations, it is shown that the satisfiability problem parameterized by certain sets of operations over the three-element set and over the unit interval, Kleene and Gödel operations, dichotomizes with respect to computational complexity. Interestingly, even in the absence of a description of the lattice of clones over the three-element set or the unit interval, the dichotomy presented is effective in that, if the parameterizing set \(F\) of Kleene or Gödel operations is finite, it is possible to decide whether or not a given satisfiability problem SAT(\textbf{A}) over an algebra \(\mathbf{A} = ([0,1],F)\) is tractable through a reduction to the Post lattice.