On the Expressibility of Stable Logic Programming
  (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 $\sigma$ of size $n$ over
a fixed alphabet $\Sigma$, there is an extensional database
$\mathit{edb}_{M,p,\sigma}$ such that there is a one-to-one correspondence
between the stable models of $\mathit{edb}_{M,p,\sigma} \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,\sigma}$ can be computed in
polynomial time from $p$, $\sigma$ and the description of $M$ and the decoding
of such accepting computations from its corresponding stable model of
$\mathit{edb}_{M,p,\sigma} \cup P_{\mathit{Trg}}$ can be computed in linear
time. A similar statement holds for Default Logic with respect to
$\Sigma_2^\mathrm{P}$-search problems\footnote{The proof of this result
involves additional technical complications and will be a subject of another
publication.}.
