# Stable-Unstable Semantics: Beyond NP with Normal Logic Programs

arXiv: https://arxiv.org/abs/1608.01835 · HTML: https://mlsanity.com/paper/1608.01835/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2016.

## Built on by (most cited first, 5 of 5)

- [Explainability via Short Formulas: the Case of Propositional Logic with Implementation](https://mlsanity.com/paper/2209.01403/) (2022)
- [An efficient solver for ASP(Q)](https://mlsanity.com/paper/2305.10021/) (2023)
- [Quantifying over Optimum Answer Sets](https://mlsanity.com/paper/2408.07697/) (2024)
- [The Stable Model Semantics for Higher-Order Logic Programming](https://mlsanity.com/paper/2408.10563/) (2024)
- [2-ASP(Q) programs with weak constraints: Complexity and efficient implementation](https://mlsanity.com/paper/2605.27338/) (2026)

## Abstract (arXiv)

Standard answer set programming (ASP) targets at solving search problems from the first level of the polynomial time hierarchy (PH). Tackling search problems beyond NP using ASP is less straightforward. The class of disjunctive logic programs offers the most prominent way of reaching the second level of the PH, but encoding respective hard problems as disjunctive programs typically requires sophisticated techniques such as saturation or meta-interpretation. The application of such techniques easily leads to encodings that are inaccessible to non-experts. Furthermore, while disjunctive ASP solvers often rely on calls to a (co-)NP oracle, it may be difficult to detect from the input program where the oracle is being accessed. In other formalisms, such as Quantified Boolean Formulas (QBFs), the interface to the underlying oracle is more transparent as it is explicitly recorded in the quantifier prefix of a formula. On the other hand, ASP has advantages over QBFs from the modeling perspective. The rich high-level languages such as ASP-Core-2 offer a wide variety of primitives that enable concise and natural encodings of search problems. In this paper, we present a novel logic programming--based modeling paradigm that combines the best features of ASP and QBFs. We develop so-called combined logic programs in which oracles are directly cast as (normal) logic programs themselves. Recursive incarnations of this construction enable logic programming on arbitrarily high levels of the PH. We develop a proof-of-concept implementation for our new paradigm. This paper is under consideration for acceptance in TPLP.