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