Heuristic Time Hierarchies via Hierarchies for Sampling Distributions

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

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.
BibTeX
@inproceedings{itsykson2015heuristic,
  author = {Dmitry Itsykson and Alexander Knop and Dmitry Sokolov},
  title = {{Heuristic Time Hierarchies via Hierarchies for Sampling Distributions}},
  booktitle = {ISAAC},
  year = {2015},
  doi = {10.1007/978-3-662-48971-0\_18},
}

Loading related content...

Figure