License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06111.3
URN: urn:nbn:de:0030-drops-6151
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/615/
Go to the corresponding Portal

van Melkebeek, Dieter ; Pervyshev, Konstantin

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

pdf-format:
06111.PervyshevKonstantin.Paper.615.pdf (0.4 MB)

Abstract

We show that for any reasonable semantic model of computation and for any positive integer $a$ and rationals $1 leq c < d$, there exists a language computable in time $n^d$ with $a$ bits of advice but not in time $n^c$ 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 efficient universal machine that can be complemented within the model in exponential time and if it is efficiently closed under deterministic transducers. 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, interactive proof protocols with one or multiple provers, etc.

BibTeX - Entry

@InProceedings{vanmelkebeek_et_al:DagSemProc.06111.3,
  author =	{van Melkebeek, Dieter and Pervyshev, Konstantin},
  title =	{{A Generic Time Hierarchy for Semantic Models With One Bit of Advice}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--39},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/615},
  URN =		{urn:nbn:de:0030-drops-6151},
  doi =		{10.4230/DagSemProc.06111.3},
  annote =	{Keywords: Time hierarchy, non-uniformity, one bit of advice, probabilistic algorithms}
}

Keywords: Time hierarchy, non-uniformity, one bit of advice, probabilistic algorithms
Collection: 06111 - Complexity of Boolean Functions
Issue Date: 2006
Date of publication: 20.11.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI