DOI

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 HeurFBPP consists of functions with distributions on their inputs that can be computed in randomized polynomial time with bounded error on all except _ fraction of inputs. We prove that for every a, δ and integer k there exists a function F : {0, 1} → {0, 1, . . . , k − 1} such that (F,U) (Formula presented.) HeurFBPP for all ∈ > 0 and for every ensemble of distributions Dn samplable in na steps, (F,D) ∈ Heur1−1/k −δFBPTime[na]. 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 P[formula presented] Heur- BPTime[nk] if one-way functions exist. We also show that our technique may be extended for time hierarchies in some other heuristic classes.

Язык оригиналаанглийский
Название основной публикацииAlgorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings
РедакторыKhaled Elbassioni, Kazuhisa Makino
ИздательSpringer Nature
Страницы201-211
Число страниц11
ISBN (печатное издание)9783662489703
DOI
СостояниеОпубликовано - 1 янв 2015
Событие26th International Symposium on Algorithms and Computation, ISAAC 2015 - Nagoya, Япония
Продолжительность: 9 дек 201511 дек 2015

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том9472
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция26th International Symposium on Algorithms and Computation, ISAAC 2015
Страна/TерриторияЯпония
ГородNagoya
Период9/12/1511/12/15

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 49785713