Каковы некоторые основные примеры успешной дерандомизации или, по крайней мере, прогресса в демонстрации конкретных доказательств достижения цели (а не связи между случайностью и жесткостью)?
Единственный пример, который мне приходит в голову, - это тестирование AKS на детерминированность полиномиального времени (даже для этого была методология, предполагающая GRH). Итак, какие конкретные доказательства на примере мы имеем для дерандомизации (опять же, не связности твердости или оракула)?
Пожалуйста, оставляйте примеры только там, где было показано улучшение сложности времени от рандомизированного поли до детерминированного поли или чего-то, что очень близко для конкретных задач.
Ниже приведен комментарий, и я не знаю, насколько он поможет в этом вопросе.
У Шазель есть очень интригующее заявление в http://www.cs.princeton.edu/~chazelle/linernotes.html в разделе «Метод расхождения: случайность и сложность (издательство Cambridge University Press, 2000)».
«Для меня было бесконечным источником восхищения, что более глубокое понимание детерминированных вычислений должно требовать мастерства рандомизации. Я написал эту книгу, чтобы проиллюстрировать эту мощную связь. От минимальных связующих деревьев до линейного программирования и триангуляции Делоне, наиболее эффективные алгоритмы часто являются дерандомизацией вероятностных решений. Метод расхождений ставит в центр внимания один из самых плодотворных вопросов во всей информатике: если вы считаете, что вам нужны случайные биты, расскажите, пожалуйста, почему?
Ответы:
.SL = L
обозначает рандомизированном logspace и R L = L является уменьшенной версией задачи R P = P . Главным шагом стало доказательство Рейнгольдом в '04 («Ненаправленная ST-связность в пространстве журналов»), что S L = L , где S означает «симметричный», а S L - промежуточный класс междуR L R L = L R P= P SL = L S SL и L .R L L
Идея состоит в том, что вы можете думать о рандомизированной машине пространства Тьюринга как о ориентированном графе полиномиального размера, где узлы - это состояния машины, а алгоритм RL выполняет случайное блуждание с хорошими свойствами. SL соответствует неориентированным графам этого вида. Доказательство Рейнгольда, основанное на работе над графами расширителей, в частности «зигзагообразным продуктом» Рейнгольда, Вадхана и Вигдерсона, позволяет произвольно обходить неориентированный граф с хорошими свойствами и превращать его в псевдослучайный обход, сохраняющий эти свойства.
редактировать этот вопрос было опубликовано до того, как вопрос был явно изменен, чтобы сосредоточиться исключительно на P против BPP ... Я оставляю его, потому что он, кажется, представляет интерес.
источник
В принципе, в BPP есть только одна интересная проблема, о которой неизвестно, что она есть в P: Проверка полиномиальной идентичности, учитывая, что алгебраическая схема является полиномом, который она генерирует тождественно равным нулю. Impagliazzo и Kabanets показывают, что PIT в P подразумевает некоторые нижние границы цепи. Таким образом, нижние границы схемы - единственная причина (но довольно хорошая), что мы считаем P = BPP.
источник
Помимо проверки полиномиальной идентичности, еще одна очень важная проблема, которая, как известно, связана с BPP, но не с P, заключается в аппроксимации перманента неотрицательной матрицы или даже числа совершенных совпадений в графе. Существует рандомизированный многовременный алгоритм для аппроксимации этих чисел в пределах (1 + eps) фактора, тогда как лучшие детерминированные алгоритмы достигают только ~ 2 ^ n факторных приближений.
В то время как постоянный является основным примером, существует много приближенных проблем подсчета, для которых существует огромный разрыв между рандомизированными алгоритмами (обычно основанными на методах «MCMC») и детерминированными алгоритмами.
Другая проблема в аналогичном ключе заключается в приближении объема явно заданного выпуклого тела (скажем, многогранник, описываемый набором линейных неравенств).
источник