Title | The Complexity of 3-Valued Lukasiewicz Rules |

Publication Type | Conference Paper |

Year of Publication | 2015 |

Authors | Bofill M [1], Manyà F [2], Vidal A [3], Villaret M [4] |

Conference Name | 12th Conference on Modeling Decisions for Artificial Intelligence (MDAI 2015) |

Volume | 9312 |

Edition | V. Torra and Y. Narukawa |

Publisher | Springer |

Conference Location | Skövde (Sweden) |

Pagination | 221-229 |

Date Published | 21/09/2015 |

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 [5] |