A Generic Time Hierarchy for Semantic Models With One Bit of Advice

Complexity of Boolean Functions

计算机科学;物理学;物理学

Preliminary version

Others  :  http://drops.dagstuhl.de/opus/volltexte/2006/615/pdf/06111.PervyshevKonstantin.Paper.615.pdf
PID  :  6448

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

We show that for any reasonable semantic model of compu-tation and for any positive integer a and rationals 1 ≤ c < d, there exists a language computable in time nd with a bits of advice but not in time nc with a bits of advice. A semantic model is one for which there exists a computable enumeration that contains all machines in the model but may also contain others. We call such a model reasonable if it has an ef- ficient universal machine that can be complemented within the model in exponential time and if it is efficiently closed under deterministic trans- ducers. Our result implies the first such hierarchy theorem for randomized ma- chines 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 yields considerably simpler proofs of known hierarchy theorems with one bit of advice for randomized and quantum machines with two-sided error. Our paradigm also allows us to derive stronger separation results in a unified way. For models that have an efficient universal machine that can be simulated deterministically in exponential time and that are efficiently closed under randomized reductions with two-sided error, we establish the following: For any constants a and c, there exists a language com- putable in polynomial time with one bit of advice but not in time nc with a log n bits of advice. In particular, we obtain such separation for randomized and quantum machines with two-sided error. For random- ized machines with one-sided error, we get that for any constants a and c there exists a language computable in polynomial time with one bit of