TitleThe Complexity of 3-Valued Lukasiewicz Rules
Publication TypeConference Paper
Year of Publication2015
AuthorsBofill M, Manyà F, Vidal A, Villaret M
Conference Name12th Conference on Modeling Decisions for Artificial Intelligence (MDAI 2015)
EditionV. Torra and Y. Narukawa
Conference LocationSkövde (Sweden)
Date Published21/09/2015

It is known that determining the satisfiability of n-valued ?ukasiewicz rules is NP-complete for n?4, as well as that it can be solved in time linear in the length of the formula in the Boolean case (when n=2). However, the complexity for n=3 is an open problem. In this paper we formally prove that the satisfiability problem for 3-valued ?ukasiewicz rules is NP-complete. Moreover, we also prove that when the consequent of the rule has at most one element, the problem is polynomially solvable