Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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 Heur∈FBPP 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.) Heur∈FBPP 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 дек 2015 → 11 дек 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/15 → 11/12/15 |
ID: 49785713