Примеры успешной дерандомизации от БПП к П

15

Каковы некоторые основные примеры успешной дерандомизации или, по крайней мере, прогресса в демонстрации конкретных доказательств достижения цели (а не связи между случайностью и жесткостью)?пзнак равноВпп

Единственный пример, который мне приходит в голову, - это тестирование AKS на детерминированность полиномиального времени (даже для этого была методология, предполагающая GRH). Итак, какие конкретные доказательства на примере мы имеем для дерандомизации (опять же, не связности твердости или оракула)?

Пожалуйста, оставляйте примеры только там, где было показано улучшение сложности времени от рандомизированного поли до детерминированного поли или чего-то, что очень близко для конкретных задач.


Ниже приведен комментарий, и я не знаю, насколько он поможет в этом вопросе.

У Шазель есть очень интригующее заявление в http://www.cs.princeton.edu/~chazelle/linernotes.html в разделе «Метод расхождения: случайность и сложность (издательство Cambridge University Press, 2000)».

«Для меня было бесконечным источником восхищения, что более глубокое понимание детерминированных вычислений должно требовать мастерства рандомизации. Я написал эту книгу, чтобы проиллюстрировать эту мощную связь. От минимальных связующих деревьев до линейного программирования и триангуляции Делоне, наиболее эффективные алгоритмы часто являются дерандомизацией вероятностных решений. Метод расхождений ставит в центр внимания один из самых плодотворных вопросов во всей информатике: если вы считаете, что вам нужны случайные биты, расскажите, пожалуйста, почему?


источник
2
Многие алгоритмы могут быть дерандомизированы с использованием общих методов, таких как метод условных ожиданий, метод пессимистических оценок и использование ограниченных выборочных пространств независимости. На самом деле, тестирование простоты и тестирование полиномиальной идентичности настолько известны, потому что они являются редкими примерами естественных функций, которые сопротивляются стандартным методам дерандомизации.
Сашо Николов
1
@SashoNikolov спасибо, возможно, комментарий может быть расширен как полный ответ на некоторых примерах. Также является ли жесткость-случайность связи через сложность схемы единственной причиной, по которой люди верят ? пзнак равноВпп
1
Я думаю, что это слишком основа для ответа. См. Главу о дерандомизации в Alon-Spencer для деталей и примеров: она охватывает три техники, которые я упомянул.
Сашо Николов
Интересная вещь о классе BPP состоит в том, что его теоретическое определение требует случайных входных битов, которые можно легко показать, используя меры рандомизации и слабой случайности коломогров, которых не существует в конечных областях. Я не знаю, как люди могут жить с этим несоответствием. Я сам не верю, что существует явный класс BPP (это либо NP, либо P).

Ответы:

18

.SLзнак равноL

обозначает рандомизированном logspace и R L = L является уменьшенной версией задачи R P = P . Главным шагом стало доказательство Рейнгольдом в '04 («Ненаправленная ST-связность в пространстве журналов»), что S L = L , где S означает «симметричный», а S L - промежуточный класс междурLрLзнак равноLрпзнак равнопSLзнак равноLSSL и L .рLL

Идея состоит в том, что вы можете думать о рандомизированной машине пространства Тьюринга как о ориентированном графе полиномиального размера, где узлы - это состояния машины, а алгоритм RL выполняет случайное блуждание с хорошими свойствами. SL соответствует неориентированным графам этого вида. Доказательство Рейнгольда, основанное на работе над графами расширителей, в частности «зигзагообразным продуктом» Рейнгольда, Вадхана и Вигдерсона, позволяет произвольно обходить неориентированный граф с хорошими свойствами и превращать его в псевдослучайный обход, сохраняющий эти свойства.

редактировать этот вопрос было опубликовано до того, как вопрос был явно изменен, чтобы сосредоточиться исключительно на P против BPP ... Я оставляю его, потому что он, кажется, представляет интерес.

усул
источник
8
Пожалуйста, не надо. Ответ интересный.
Эмиль Йержабек поддерживает Монику
1
Привет, @Student. Я думаю, что люди, пришедшие на вопрос, заинтересованные примерами успешной дерандомизации, будут заинтересованы в этом ответе, поэтому я оставлю его без значения неуважения к вашим целям (которые были отредактированы только позже, чтобы указать сложность времени ... )
усуль
2
Я также должен сказать, что вопросы и ответы на этом сайте должны быть сформулированы таким образом, чтобы они в целом были полезны для будущих посетителей в качестве справочного ресурса, а не только для удовлетворения конкретных целей автора. Я, например, нахожу вопрос без искусственных ограничений сложности времени и BPP гораздо более полезным.
Эмиль Йержабек поддерживает Монику
@ EmilJeřábek Хорошо, спасибо, мы оставим пост Усула, как здесь.
@usul 'Идея состоит в том, что вы можете думать о рандомизированной машине пространства Тьюринга как о ориентированном графе полиномиального размера'. Есть ли подходящая интуиция, которая работает на NL? Я знаю, что L - это не NL, но PSPACE = NPSPACE, поэтому пространство может отличаться от времени.
T ....
16

В принципе, в BPP есть только одна интересная проблема, о которой неизвестно, что она есть в P: Проверка полиномиальной идентичности, учитывая, что алгебраическая схема является полиномом, который она генерирует тождественно равным нулю. Impagliazzo и Kabanets показывают, что PIT в P подразумевает некоторые нижние границы цепи. Таким образом, нижние границы схемы - единственная причина (но довольно хорошая), что мы считаем P = BPP.

Лэнс Фортноу
источник
4
Хотя я согласен с вами на высоком уровне, я думаю, что множество рандомизированных алгоритмов в теории вычислительных групп предлагает еще один тесно связанный класс интересных вопросов дерандомизации, которые, похоже, не сводятся к PIT. Хотя большинство из них являются функциями, а не проблемами решения, некоторые из них могут быть преобразованы в интересные проблемы решения в BPP, например, cstheory.stackexchange.com/a/11440/129
Джошуа
О(е(N))О(е(N))ВппВппе(N) выражение, является подэкспонатом, а все детерминированные алгоритмы находятся в эксп. Имеет липзнак равноВпп
12

Помимо проверки полиномиальной идентичности, еще одна очень важная проблема, которая, как известно, связана с BPP, но не с P, заключается в аппроксимации перманента неотрицательной матрицы или даже числа совершенных совпадений в графе. Существует рандомизированный многовременный алгоритм для аппроксимации этих чисел в пределах (1 + eps) фактора, тогда как лучшие детерминированные алгоритмы достигают только ~ 2 ^ n факторных приближений.

В то время как постоянный является основным примером, существует много приближенных проблем подсчета, для которых существует огромный разрыв между рандомизированными алгоритмами (обычно основанными на методах «MCMC») и детерминированными алгоритмами.

Другая проблема в аналогичном ключе заключается в приближении объема явно заданного выпуклого тела (скажем, многогранник, описываемый набором линейных неравенств).

Рагху Мека
источник
Одна тонкость в P против BPP, которую я хотел бы понять лучше, это разница между функциональными проблемами и проблемами решения. Может случиться так, что существует много функциональных задач, которые решаются (в некотором смысле) случайно, но не детерминистически за полиномиальное время, но P = BPP. Кажется, что ваши примеры, вероятно, легко переводятся в решение проблем, верно?
Усул
1
Решение по сравнению с проблемами функций немного сложнее, чем в мире NP, но все же многое известно: например, в этой статье в разделе 3 приведен пример «рандомизированной многократной задачи поиска с временным разрешением», которая даже не разрешима. Но если функция взаимно-однозначная, то P = BPP подразумевает, что «случайная задача с поли-временными функциями» имеет детерминированный алгоритм с поли-временем (в статье также приводится много других примеров)
Джо Бебель,