Complexity of fuzzy answer set programming under Łukasiewicz semantics
| Autor: | Marjon Blondeel, Steven Schockaert, Dirk Vermeir, Martine De Cock |
|---|---|
| Přispěvatelé: | Theoretical Computer Science, Logic Engineering, Informatics and Applied Informatics |
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: |
Polynomial hierarchy
Reduction (recursion theory) Theoretical computer science Computational complexity theory Computer science Semantics (computer science) Applied Mathematics Answer set programming DESCRIPTION LOGIC PROGRAMS Science General Fuzzy logic BOUND ALGORITHM Theoretical Computer Science WEB Computational complexity Lukasiewicz logic BRANCH Artificial Intelligence Lukasiewicz Logic Łukasiewicz logic Software answer set programming Integer (computer science) |
| Zdroj: | INTERNATIONAL JOURNAL OF APPROXIMATE REASONING |
| ISSN: | 0888-613X |
| Popis: | Fuzzy answer set programming (FASP) is a generalization of answer set programming (ASP) in which propositions are allowed to be graded. Little is known about the computational complexity of FASP and almost no techniques are available to compute the answer sets of a FASP program. In this paper, we analyze the computational complexity of FASP under Łukasiewicz semantics. In particular we show that the complexity of the main reasoning tasks is located at the first level of the polynomial hierarchy, even for disjunctive FASP programs for which reasoning is classically located at the second level. Moreover, we show a reduction from reasoning with such FASP programs to bilevel linear programming, thus opening the door to practical applications. For definite FASP programs we can show P-membership. Surprisingly, when allowing disjunctions to occur in the body of rules - a syntactic generalization which does not affect the expressivity of ASP in the classical case - the picture changes drastically. In particular, reasoning tasks are then located at the second level of the polynomial hierarchy, while for simple FASP programs, we can only show that the unique answer set can be found in pseudo-polynomial time. Moreover, the connection to an existing open problem about integer equations suggests that the problem of fully characterizing the complexity of FASP in this more general setting is not likely to have an easy solution. The complexity of the main reasoning tasks for disjunctive FASP is NP-complete.There is a reduction from reasoning in FASP to bilevel linear programming.We connect the complexity to an existing open problem about integer equations. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect