Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
We study the class AvgBPP that consists of distributional problems which can be solved in average polynomial time (in terms of Levin's average-case complexity) by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for AvgBPP under polynomial time samplable distributions. Since we use deterministic reductions, the existence of a deterministic algorithm with average polynomial running time for our problem would imply AvgP=AvgBPP. Note that, while it is easy to construct a promise problem that is complete for promise-BPP, it is unknown whether BPP contains complete languages. We also prove a time hierarchy theorem for AvgBPP (there are no known time hierarchy theorems for BPP). We compare average-case classes with their classical (worst-case) counterparts and show that the inclusions are proper.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 213-223 |
Число страниц | 11 |
Журнал | Annals of Pure and Applied Logic |
Том | 162 |
Номер выпуска | 3 |
DOI | |
Состояние | Опубликовано - 1 дек 2010 |
Опубликовано для внешнего пользования | Да |
ID: 49786895