ACT Seminar: Dieter van Melkebeek/University of Wisconsin Time Hierarchies for Semantic Models of Computation in TAY 3.128

Contact Name: 
Jenna Whitney
Date: 
Apr 28, 2006 11:00am - 12:00pm

Speaker Name/Affiliation: Dieter van Melkebeek/Un

iversity of Wisconsin

Talk Title: Time Hierarchies for Semantic Mo

dels of Computation

Date/Time: April 28 2006 at 11:00 a.m.

Coffee: 10:45 a.m.

Location: TAY 3.128

Host: Anna Gal
<

br>Talk Abstract:
A basic question in computational complexity asks whet

her somewhat
more time allows us to solve strictly more decision proble

ms 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 fo

r everything else where we call a model syntactic if there
exists a co

mputable enumeration consisting exactly of the machines
in the model.
There has been significant progress in recent years namely
in es

tablishing time hierarchies for non-syntactic models with
small advice.
In this talk we survey these results and present a generic theorem that c

aptures and strengthens all of them. We show that for virtually any semanti

c model of computation and for any rationals 1 <= c < d there exists a lan

guage computable in time n%5Ed with one bit of advice but not in time n%5Ec
with one bit of advice where we call a model semantic if there exists a c

omputable 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 on

e-
or zero-sided error unambiguous machines symmetric alternation Ar

thur-Merlin games of any signature etc. Our argument also yields considera

bly 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.