TIME: 2:30-3:20 pm,  Wednesday, May 24, 2006

PLACE: CSE 691 (Gates Commons)

TITLE: Time Hierarchies for Semantic Models of Computation

SPEAKER:  Dieter van Melkebeek
          University of Wisconsin

ABSTRACT:
A basic question in computational complexity asks whether somewhat more
time allows us to solve strictly more decision problems on a given model
of computation. Despite its fundamental nature, the question remains
unanswered for many models of interest. Essentially, time hierarchies
are known for every syntactic model of computation but open for
everything else, where we call a model syntactic if there exists a
computable enumeration consisting exactly of the machines in the
model.

There has been significant progress in recent years, namely in
establishing time hierarchies for non-syntactic models with small advice.
In this talk, we survey these results and present a generic theorem that
captures and strengthens all of them. We show that for virtually any
semantic model of computation and for any rationals 1 <= c < d, there
exists a language computable in time n^d with one bit of advice but not
in time n^c with one bit of advice, where we call a model semantic if
there exists a computable enumeration that contains all machines in
the model but may also contain others.

Our result implies the first such hierarchy theorem for randomized
machines with zero-sided error, quantum machines with one- or zero-sided
error, unambiguous machines, symmetric alternation, Arthur-Merlin games
of any signature, etc. Our argument also yields considerably simpler
proofs of earlier hierarchy theorems with one bit of advice for
randomized or quantum machines with two-sided error.

Based on joint work with Konstantin Pervyshev.