TítuloThe 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)
Volume9312
EditionV. Torra and Y. Narukawa
EditorialSpringer
Conference LocationSkövde (Sweden)
Paginación221-229
Date Published21/09/2015
Resumen

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

URLhttp://link.springer.com/chapter/10.1007/978-3-319-23240-9_18