Algorithms and Complexity Seminar
Thursday, May 11, 2006, 4-5:15pm in 32-G575.
Time Hierarchies for Semantic Models of Computation
Dieter van Melkebeek (U. Wisconsin)
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.
This is joint work with Konstantin Pervyshev.
Host: Madhu Sudan