Polynomial-time Computable Logic Programs
Yuri G. Ventsov
Department of Computer Science,
Monash University,
Clayton 3168, Australia.
iouriv@bruce.cs.monash.edu.au
John N. Crossley
Department of Computer Science,
Monash University,
Clayton 3168, Australia.
jnc@bruce.cs.monash.edu.au
Abstract
We show that if a logic program P is such that, for each
term $t$, there is a polynomial $p(x)$ such that for all extensions
$t'$ of $t$ the program runs in time $p(|t'|)$, i.e. runs in
polynomial-time locally, then there is a single polynomial $p_0$ such
that P runs in time $p_0(|t|)$ for all terms $t$. We also
show that there is no algorithm which given P returns $p_0$
for all programs P which run in polynomial-time.
Conference Home Page