Title: Lewis Dichotomies in Many-Valued Logics
Speaker: Simone Bova, Department of Mathematics, Vanderbilt,
University (Nashville, USA)
Abstract: A classical result by Harry Lewis in 1979 shows that the
computational complexity of the satisfiability problem of Boolean
logic dichotomizes, depending on the Boolean operations available to
formulate the instance: intractable (NP-complete) if negation of
implication is definable, and tractable (in P) otherwise. Exploiting
Post lattice and clone theory, we investigate Lewis dichotomies
for a number of many-valued generalizations of Boolean propositional
logic, namely Kleene, DeMorgan, and Godel logics. We obtain a
complete dichotomy classification for Kleene and Godel logics. We
give a lower bound for DeMorgan logic, and raise the dichotomy problem
for finite-valued Lukasiewicz logic.