Complexity of fuzzy answer set programming under Lukasiewicz semantics: First results

Fuzzy answer set programming (FASP) has recently been proposed as a generalization of answer set programming in which propositions are allowed to be graded. Little is known about its computational complexity. In this paper we present some results and reveal a connection to an open problem about integer equations, suggesting that characterizing the complexity of FASP may not be straightforward.

Publication year:2011

Keywords:Fuzzy Answer Set Programming, Lukasiewicz logic, Complexity