Advertisement
Published in:
2015 | OriginalPaper | Chapter
Heuristic Time Hierarchies via Hierarchies for Sampling Distributions
Authors : Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.