ASP-QRAT: A Conditionally Optimal Dual Proof System for ASP

Leroy Chew, Alexis de Colnet, Stefan SzeiderKR 2024 · DOI

TL;DR

This paper introduces ASP-QRAT, a novel proof system for Answer Set Programming (ASP) that can certify both consistent and inconsistent ASP programs. By translating ASP problems into Quantified Boolean Formulas (QBFs) and leveraging the QRAT proof system, ASP-QRAT offers a unified and efficient way to verify ASP solver outputs, with theoretical implications for computational complexity.

What Problem Does This Paper Address?

Answer Set Programming (ASP) is a powerful declarative programming paradigm used for knowledge representation and reasoning. When an ASP solver determines a program is consistent (has answer sets) or inconsistent (has no answer sets), it's crucial to have a verifiable certificate for this decision. While methods exist for verifying consistency, certifying inconsistency, especially for complex ASP programs with disjunctions, has been a challenge. Existing proof systems for inconsistent ASPs (like ASP-DRUPE) are often specialized. This paper aims to provide a unified, efficient, and theoretically well-founded proof system for both consistency and inconsistency checking in ASP.

Methods

The core of ASP-QRAT is a translation of ASP programs into Quantified Boolean Formulas (QBFs). Specifically, the authors leverage the QRAT proof system, a well-established system for QBFs. The translation involves:

  • Clark's Completion: Transforming ASP rules into a propositional formula.
  • Loop Formulas: Generating additional clauses to handle the minimization required by ASP's stable model semantics, particularly for programs with loops.
  • QBF Translation: Encoding the ASP consistency problem into a QBF of the form $\exists X \forall Y \exists Z \Phi$, where $X$ represents atom variables, $Y$ represents loop slot variables, and $Z$ represents Tseitin variables for definitions.
  • QRAT Proof System: Utilizing the inference rules of QRAT (ATA, ATE, ORATA, ORATE, IRATA, IRATE, Local-Purity) to construct proofs for the translated QBF. These rules allow for adding/removing clauses based on logical equivalence and purity, enabling efficient proof construction and checking.

The system is "dual" because it can handle both consistency (satisfaction mode) and inconsistency (refutation mode) proofs.

Datasets

Not discussed in the paper. The paper focuses on a theoretical proof system and its properties, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Unified Proof System: ASP-QRAT provides a single framework to certify both consistency and inconsistency of ASP programs, bridging a gap in existing ASP verification tools.
  • QBF as a Bridge: Leveraging QBFs and the QRAT proof system offers a powerful and general mechanism for ASP verification, benefiting from established QBF research.
  • Conditional Optimality: The paper demonstrates that ASP-QRAT is "conditionally optimal." This means that proving a super-polynomial lower bound for ASP-QRAT would imply a major breakthrough in theoretical computer science (e.g., proving $NP \neq P/poly$ or establishing lower bounds for extended resolution). This is a significant theoretical result.
  • Dual Nature: The system's ability to handle both satisfaction and refutation modes makes it a versatile tool for ASP verification.
  • Novel ASP to QBF Translation: The translation used is not the standard one but relies on Clark's Completion and loop formulas, fitting well with modern ASP solver internals.

Key Results

  • Soundness and Completeness: ASP-QRAT is proven to be sound (proofs correctly reflect ASP consistency/inconsistency) and complete (a proof exists if and only if the ASP is consistent/inconsistent).
  • P-simulation of ASP-DRUPE: ASP-QRAT can p-simulate ASP-DRUPE, an existing refutation system for inconsistent ASPs, meaning ASP-DRUPE proofs can be converted to ASP-QRAT proofs with only a polynomial increase in size.
  • Conditional Optimality for ASP: The paper establishes conditional optimality for ASP-QRAT, linking its proof complexity to fundamental open problems in computational complexity theory, particularly concerning extended resolution. This is highlighted as a remarkable achievement, especially for consistent ASPs where no analogous result exists for QBFs.
  • Extraction of Answer Sets: A satisfaction proof in ASP-QRAT can be used to extract an answer set for a consistent ASP program.

Limitations and Future Work

  • Theoretical Focus: The paper primarily presents a theoretical framework. While it discusses how the system could be implemented in ASP solvers, empirical evaluation of its performance in practice is not detailed.
  • Complexity of Translation: While the QBF translation is polynomial in the size of the ASP program, the resulting QBFs can still be complex, and the efficiency of QRAT proof checking on these QBFs in practice is an open question.
  • Future Research: The authors suggest extending the system to certify ASPs with quantifiers and exploring its implementation in practical ASP solvers. Further research into the exact relationship between ASP-QRAT and other proof systems, especially concerning lower bounds, is also indicated.

Summary updated

BibTeX
@inproceedings{chew2024asp,
  author = {Leroy Chew and Alexis de Colnet and Stefan Szeider},
  title = {{ASP-QRAT: A Conditionally Optimal Dual Proof System for ASP}},
  booktitle = {KR},
  year = {2024},
  doi = {10.24963/kr.2024/24},
}
Figure