В одном предложении: подразумевает ли существование иерархии для какие-либо результаты дерандомизации?
но неопределенный вопрос: подразумевает ли существование иерархии для какие-либо трудные нижние границы? Влияет ли решение этой проблемы на известный барьер в теории сложности?
Моя мотивация для этого вопроса состоит в том, чтобы понять относительную сложность (относительно других основных открытых проблем в теории сложности) показа иерархии для . Я предполагаю, что все считают, что такая иерархия существует, но, пожалуйста, поправьте меня, если вы думаете иначе.
Немного предыстории : содержит те языки, членство которых может быть определено вероятностным токарным станком за время f ( n ) с ограниченной вероятностью ошибки. Точнее говоря, язык L ∈ B P T I M E ( f ( n ) ), если существует вероятностная машина Тьюринга T такая, что для любого x ∈ L машина T работает за время O ( f ( | x | ) И принимает с вероятностьюпо меньшей мере 2 / 3 , и для любого х ∉ L , Т пробегает по времени O ( F ( | х | ) ) и отклоняет с вероятностьюпо меньшей мере 2 / 3 .
Безусловно, открыто, является ли для всех c > 1 . Барак показал, что существует строгая иерархия для B P T I M E для машин с O ( log n )совет. Fortnow и Santhanam улучшили это до 1 совета. Это заставляет меня думать, что доказательство существования вероятностной иерархии времени не так уж далеко. С другой стороны, результат все еще открыт, и я не могу найти никакого прогресса после 2004 года. Ссылки, как обычно, можно найти в зоопарке .
Отношение к дерандомизации исходит из результатов Импальяццо и Вигдерсона: они показали, что в предположении вероятной сложности для любой константы d и некоторой константы c . Согласно классическим теоремам иерархии времени для детерминированного времени, это подразумевает иерархию времени для вероятностного времени. Я задаю обратный вопрос: вероятностный высокоуровневый удар по барьеру, связанному с доказательством результатов дерандомизации?
РЕДАКТИРОВАТЬ: Я принимаю ответ Райана как более полное решение.
Если у кого-то есть наблюдения о том, что стоит между нами и доказывает существование иерархии для вероятностного времени, не стесняйтесь отвечать / комментировать. Конечно, очевидный ответ заключается в том, что имеет семантическое определение, которое не поддается классическим методам. Меня интересуют менее очевидные наблюдения.
источник
Нетрудно вывести вероятностную иерархию времени, если BPP = EXP, крайний случай отсутствия дерандомизации.
источник