Структурная сложность вероятностных вычислений с ограниченной ошибкой

На данный момент для вероятностных вычислений с ограниченной ошибкой не известно теоремы об иерархии по времени, также не известно полных задач в классе $BPP$ относительно детерминированных сведений. Основное препятствие — это отсутствие вычислимой нумерации вероятностных машин, которые удовлетворяют условию ограниченной ошибки. Хартманис и Хемачандра в 1986 году показали, что существует такой оракул $A$, что в классе $BPP^A$ нет полных языков. Барак в 2002 году показал, что если существует полная задача в классе BPP относительно достаточно сильных детерминированных сведений, то существует и иерархии по времени. Лучший результат, связанный с иерархией по времени суперполиномиальный: Карпинский и Вербик показали, что $BPTime[n^{\log n}]$ строго содержится в $BPTime[2^{n^c}]$ для $c>0$.
В серии работ (Барак 2002), (Фортноу, Сансанам 2004) и (Мелкебик, Первышев 2007) доказывается иерархия по времени для вероятностных вычислений с ограниченной ошибкой, использующих несколько битов (в лучшем результате используется всего один бит) неравномерной подсказки. Фортноу и Сансанам в 2004 году доказали теорему об иерархии по времени для эвристических алгоритмов, такие алгоритмы могут выдавать неверный ответ на маленькой доле входов. Первышев в 2007 году существенно упростил это доказательство.
Докладчиком построена полная задача относительно детерминированных сведений по Тьюрингу и доказана теорема об иерархии по времени в классе $AvgBPP$, который состоит из распределенных задач (языка и полиномиально моделируемого распределения), которые можно решить за полиномиальное в среднем случае (в смысле определения Левина) время вероятностными алгоритмами с ограниченной ошибкой.