NP-completeness of fuzzy answer set programming under Łukasiewicz semantics
Marjon Blondeel, Steven Schockaert, Martine De Cock, Dirk Vermeir · Ghent University Academic Bibliography (Ghent University) · 2012
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 first present an overview of previous results on the computational complexity of FASP under Łukasiewicz semantics, after which we show NPcompleteness for normal and disjunctive FASP programs.Moreover, for this type of FASP programs we will show a reduction to bilevel linear programming, thus opening the door to practical applications.