Jochen Messner
Abstract:
A deterministic algorithm O accepting a language L is called
(polynomially) optimal if for any algorithm A accepting L
there is a polynomial p such that time(O,x) <=
p(|x| + time(A,x)) for every x in L. It
is shown that an optimal acceptor for a language L exists if there is
a p-optimal proof system for L. If L is a p-cylinder also the
inverse implication holds. This result widely generalizes work from
Krajícek and Pudlák who showed the result for L= TAUT. It is
further shown how to construct an optimal acceptor for a p-cylinder
L, given an acceptor for L that runs fast on every easy subset
of L. Then we investigate the relationship of this notion of an
`optimal acceptor' to a more general notion of optimality. Here, instead of
considering time-complexity on each individual string x, worst-case
time-bounds are considered. It is observed that every set complete for
exponential time under linearly length-bounded polynomial-time many-one
reducibility has an acceptor with an optimal time-bound whereas on the other
hand no set hard for exponential time under polynomial-time many-one
reducibility has a p-optimal proof system. Finally we show how these
results can be translated to nondeterministic algorithms and optimal proof
systems.