@conference {5474,
title = {The Complexity of 3-Valued Lukasiewicz Rules},
booktitle = {12th Conference on Modeling Decisions for Artificial Intelligence (MDAI 2015)},
volume = {9312},
year = {2015},
month = {21/09/2015},
pages = {221-229},
publisher = {Springer},
organization = {Springer},
edition = {V. Torra and Y. Narukawa},
address = {Sk{\"o}vde (Sweden)},
abstract = {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},
url = {http://link.springer.com/chapter/10.1007/978-3-319-23240-9_18},
author = {Miquel Bofill and Felip Many{\`a} and Amanda Vidal and Mateu Villaret}
}