Abstract für Paper
Autor: Rainer Schuler and Christoph Karg
Extended abstract appears in ISAAC 1995
Abstract:
In 1990 Schapire gave an equivalent characterization of
Levin's notion of functions, that are polynomial on average. This
characterization gives a very smooth translation from worst case
complexity to average case complexity of the notions for time and
space complexity. We prove tight space- and time-hierarchy
theorems and discuss the structure of deterministic and
nondeterministic average case complexity classes. In particular,
we show for polynomial and exponential time-bounded classes that
nondeterministic average case is equivalent to deterministic
average case if this is true in worst case complexity. We
consider tally encodings of randomized decision problems and show
that there are tally randomized decision problems in average
nondeterministic polynomial time which are not in average
deterministic polynomial time if and only if average deterministic
exponential time is different from average nondeterministic
exponential time.
Kontaktadresse:
chkarg@informatik.uni-ulm.de