Computing H-Partitions in ASP and Datalog

Answer Set Programming (ASP) is a powerful programming paradigm that allows for an easy encoding of decision problems in NP. If the answer to a problem in NP is "yes," then, by definition, there is a "yes"-certificate that can be checked in polynomial time. In an ASP guess-and-check program, a programmer first declares the format of such a certificate, and then specifies the constraints that a well-formatted certificate should obey in order to be a "yes"- certificate. For example, for the well-known problem SAT, an ASP-programmer can first declare that certificates take the form of truth assignments, and then specify that "yes"-certificates are those certificates that leave no clause unsatisfied. While ASP guess-and-check programs are typically oriented towards NP-complete problems, they can also be used for problems in P. For example, the previously mentioned encoding of SAT also solves 2SAT, which is known to be in P. This raises the following issue which will be addressed in this paper. Assume that we have an answer set solver at our disposal, and that we have written a guess-and-check ASP program for a particular problem that is NPcomplete in general (for example, SAT). Assume furthermore that we know that under some restrictions, the problem can be solved in polynomial time (for example, the restriction of SAT to 2SAT).