On the Expressibility of Stable Logic Programming
| dc.creator | Marek, Victor W. | |
| dc.creator | Remmel, Jeffrey B. | |
| dc.date | 2003-12-22 | |
| dc.date.accessioned | 2026-07-07T03:20:47Z | |
| dc.date.available | 2026-07-07T03:20:47Z | |
| dc.description | (We apologize for pidgin LaTeX) Schlipf \cite{sch91} proved that Stable Logic Programming (SLP) solves all $\mathit{NP}$ decision problems. We extend Schlipf's result to prove that SLP solves all search problems in the class $\mathit{NP}$. Moreover, we do this in a uniform way as defined in \cite{mt99}. Specifically, we show that there is a single $\mathrm{DATALOG}^{\neg}$ program $P_{\mathit{Trg}}$ such that given any Turing machine $M$, any polynomial $p$ with non-negative integer coefficients and any input $σ$ of size $n$ over a fixed alphabet $Σ$, there is an extensional database $\mathit{edb}_{M,p,σ}$ such that there is a one-to-one correspondence between the stable models of $\mathit{edb}_{M,p,σ} \cup P_{\mathit{Trg}}$ and the accepting computations of the machine $M$ that reach the final state in at most $p(n)$ steps. Moreover, $\mathit{edb}_{M,p,σ}$ can be computed in polynomial time from $p$, $σ$ and the description of $M$ and the decoding of such accepting computations from its corresponding stable model of $\mathit{edb}_{M,p,σ} \cup P_{\mathit{Trg}}$ can be computed in linear time. A similar statement holds for Default Logic with respect to $Σ_2^\mathrm{P}$-search problems\footnote{The proof of this result involves additional technical complications and will be a subject of another publication.}. | |
| dc.description | 17 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0312053 | |
| dc.identifier | http://arxiv.org/abs/cs/0312053 | |
| dc.identifier | TCLP 3(2003), pp. 551-567q | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31948 | |
| dc.subject | Artificial Intelligence | |
| dc.subject | F.4.1 | |
| dc.title | On the Expressibility of Stable Logic Programming | |
| dc.type | text |