###
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