Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Heuristic Time Hierarchies via Hierarchies for Sampling Distributions
verfasst von : Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We introduce a new framework for proving the time hierarchy theorems for heuristic classes. The main ingredient of our proof is a hierarchy theorem for sampling distributions recently proved by Watson [11]. Class \(\mathrm {Heur}_{\epsilon }{\mathbf {FBPP}}\) consists of functions with distributions on their inputs that can be computed in randomized polynomial time with bounded error on all except \(\epsilon \) fraction of inputs. We prove that for every a, \(\delta \) and integer k there exists a function \({F: \{0, 1\}^* \rightarrow \{0, 1, \dots , k - 1\}}\) such that \((F, U) \in \mathrm {Heur}_{\epsilon }{\mathbf {FBPP}}\) for all \(\epsilon > 0\) and for every ensemble of distributions \(D_n\) samplable in \(n^a\) steps, \((F, D) \notin \mathrm {Heur}_{1 - \frac{1}{k} - \delta }{\mathbf {FBPTime}}[n^a]\). This extends a previously known result for languages with uniform distributions proved by Pervyshev [9] by handling the case \(k > 2\). We also prove that \({\mathbf {P}}\not \subseteq \mathrm {Heur}_{\frac{1}{2} - \epsilon }{\mathbf {BPTime}}[n^k]\) if one-way functions exist.
We also show that our technique may be extended for time hierarchies in some other heuristic classes.