Complexity of fuzzy answer set programming under Lukasiewicz semantics

Marjon Blondeel, Steven Schockaert, Dirk Vermeir, Martine De Cock

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


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 Lukasiewicz 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.
Original languageEnglish
Pages (from-to)1971-2003
Number of pages33
JournalInternational Journal of Approximate Reasoning
Issue number9
Publication statusPublished - 2014


  • Answer set programming
  • Lukasiewicz logic
  • Computational complexity


Dive into the research topics of 'Complexity of fuzzy answer set programming under Lukasiewicz semantics'. Together they form a unique fingerprint.

Cite this