On the Expressibility of Stable Logic

Title: On the Expressibility of Stable Logic

Research Question: Can Stable Logic Programming (SLP) solve all search problems in the class NP?

Methodology: The researchers used a uniform approach as defined in (MT99) to prove that SLP can solve all search problems in the class NP. They specifically showed that there is a single DATALOG⁺-program PTrg such that, given any Turing machine M, any polynomial p with non-negative integer coefficients, and any input σ of size no greater than a fixed alphabet Σ, there is an extensional database edbM,p,σ such that there is a one-to-one correspondence between the stable models of edbM,p,σ ∪ PTrg and the accepting computations of the machine M that reach the final state in at most p(n) steps. Moreover, edbM,p,σ can be computed in polynomial time from p,σ, and the description of M and the decoding of such accepting computations from their corresponding stable models of edbM,p,σ ∪ PTrg can be computed in linear time. A similar statement holds for Default Logic with respect to ΣP⁻2-search problems.

Results: The researchers proved that SLP can solve all search problems in the class NP. They presented a single DATALOG⁺-program PTrg that can be used to solve these problems uniformly. They also showed that the stable models of the program can be used to decode the accepting computations of the Turing machine, and that these computations can be found in linear time.

Implications: The results of this study have significant implications for the field of Answer Set Programming. By proving that SLP can solve all search problems in the class NP, the researchers have expanded the expressibility of SLP and its extensions, such as Disjunctive Logic Programming (GL91; ELM+97). This could lead to new applications and domains for ASP systems, including planning, product configuration, combinatorial optimization problems, and other areas. Furthermore, the uniform approach used in this study could serve as a template for other research in the field, potentially leading to further advancements in ASP and related areas.

Link to Article: https://arxiv.org/abs/0312053v1 Authors: arXiv ID: 0312053v1