A New Algorithm for Answer Set Computation
Giuliano Grossi, Massimo DE MARCHI · 2005
Abstract. A new exact algorithm for computing answer sets of logic programs is presented and analyzed. The algorithm takes a logic program in Kernel normal form as an input and computes its answer sets by reducing the problem to a suitable version of graph colorability. Even though worst-case complexity is exponential, thanks to a straightforward formulation we can prove that the algorithm works in time O ∗ (1.6181 n), which is asymptotically better than the trivial bound O ∗ (2 n) of the brute force algorithms. We argue that this new algorithm represents a significant progress in terms of worst-case time complexity over traditional branch-and-bound algorithms. 1