Почему случайность оказывает более сильное влияние на сокращения, чем на алгоритмы?

36

Предполагается, что случайность не расширяет возможности алгоритмов полиномиального времени, то есть предполагается, что будет выполняться. С другой стороны, случайность, по-видимому, оказывает совершенно иное влияние на сокращение полиномиального времени . По хорошо известным результатам Valiant и Vazirani, сокращается до посредством рандомизированного полиномиального сокращения времени. Маловероятно, что сокращение может быть дерандомизировано, так как оно приведет к , что считается маловероятным.P=BPPU S A T N P = U PSATUSATNP=UP

Интересно, в чем может быть причина этой асимметричной ситуации: дерандомизация представляется вполне возможной в вероятностных алгоритмах полиномиального времени, но не в вероятностных полиномиальных сокращениях времени?

Андрас Фараго
источник
3
Я предполагаю, что причина в том, что случайность помогает, когда вычисления интерактивны (например, предотвращают обман другого игрока), и сокращение можно считать очень простым видом интерактивных вычислений.
Каве
11
Какие есть доказательства того, что NP не равен UP?
Сашо Николов
Другая ситуация, в которой случайность, кажется, имеет значение, - это «алгоритмы оракула ценности». Например, хотя существует рандомизированный алгоритм 1/2 аппроксимации для неограниченного субмодулярного максимизации, самый известный детерминистический алгоритм - только 1/3 аппроксимация. Аппроксимация 1/2, как известно, является оптимальной, а аппроксимация 1/3 считается оптимальной, по крайней мере, одним из авторов.
Юваль Фильмус
@Yuval, не могли бы вы расширить свой комментарий в ответ? Мне было бы интересно прочитать более подробное объяснение.
Каве
4
Отличный вопрос!
Гил Калай

Ответы:

28

Во-первых, позвольте мне прокомментировать конкретный случай сокращения Валиант-Вазирани; это, я надеюсь, поможет прояснить общую ситуацию.

Сокращение Valiant-Vazirani можно рассматривать / определять несколькими способами. Эта редукция «пытается» отобразить выполнимую булеву формулу в однозначно выполнимую F , а неудовлетворенную F - в неудовлетворительную F . Все выходные формулы всегда получаются путем дальнейшего ограничения F , поэтому неудовлетворенность всегда сохраняется. Сокращение может быть определено либо как вывод одного F ' , либо как вывод списка F ' 1 , , F ' t . В последнем случае «успех» в случае F FFFFFFF1,,Ft определяется как наличиепо меньшей мере одногооднозначно выполнимого F ' i в списке. Назовите эти два варианта «синглтон сокращением» и «сокращением списка» соответственно (это не стандартная терминология).FSATFi

Первый момент, который важно отметить, заключается в том, что вероятность успеха в синглтон-редукции довольно мала, а именно где n - количество переменных. Трудности в улучшении этой вероятности успеха рассматриваются в статье.Θ(1/n)n

"Является ли вероятность изоляции Валиант-Вазирани улучшенной?" Dell и соавт.

http://eccc.hpi-web.de/report/2011/151/#revision1

В сокращении списка вероятность успеха может быть сделана большой, скажем, , с помощью списка размером в поли ( n ) . (Например, можно просто повторить одноэлементное сокращение много раз.)12n(n)

Теперь совсем не очевидно и не интуитивно понятно, что мы должны иметь возможность напрямую дерандомизировать редукцию, которая имеет только вероятность успеха . Действительно, ни один из результатов «жесткость-случайность» не дает гипотез, согласно которым мы можем сделать это в этом случае. Гораздо более вероятно, что сокращение списка может быть дерандомизировано (с несколько большим списком). Заметим, однако, что это не подразумевает N P = U P : наш выходной список формул может иметь много однозначно удовлетворяемых формул и, возможно, некоторые со многими удовлетворяющими назначениями, и кажется безнадежным пытаться определить однозначно приемлемое вычисление для такого список. 1/nNP=UP

Даже если бы мы могли каким - то образом дать список обжатие , в котором выполнимо всегда индуцированный список F ' 1 , ... , F ' т , где большинство из F ' J «s однозначно выполнимо, нет четкого способа превратить это в детерминированное синглтон-редукция для изоляции. Основная трудность заключается в том, что мы не знаем ни одной «операции приближенного большинства для однозначно выполнимых формул», то есть сокращения R ( F 1 , , F t )FF1,,FtFjR(F1,,Ft)выход которого однозначно выполним , если большинство «s однозначно выполним и невыполним , если большинство F ' J » s является невыполнимым. Это также кажется общим явлением: сокращения выводят более сложные объекты, чем алгоритмы принятия решений, и свойства этих объектов сложнее проверить, поэтому сложнее объединить многие из этих объектов в один объект, который наследует некоторые свойства большинства.FjFj

Для случая Валианта-Вазирани даже при вероятных предположениях дерандомизации маловероятно, что мы сможем получить , то есть детерминистически свести выполнимые формулы к выполнимым формулам с poly ( n ) решения. Интуитивно это вытекает из того факта, что процедура выделения не имеет представления даже о приблизительном размере набора решений формулы F, которая ей дана.NP=FewP(n)F

Энди Друкер
источник
1
Я желаю, чтобы каждый, кто когда-либо узнал о Valiant-Vazirani, прочитал этот ответ. Недоразумение , что derandomizing VV будет означать NP = UP , к сожалению , и упорно повторяется, и это дает четкое обсуждение вопросов и альтернатив , участвующих.
Джошуа Грохов
13

В мире оракулов легко привести примеры, когда случайность дает нам гораздо больше силы. Рассмотрим, например, проблему нахождения нуля сбалансированной булевой функции. Рандомизированный алгоритм выполняет это, используя запросов с постоянной вероятностью успеха, в то время как любой детерминированный алгоритм требует как минимум n / 2 запросов.O(1)n/2

Вот еще одна ситуация, когда предполагается, что рандомизация помогает. Предположим, мы хотим максимизировать монотонную субмодульную функцию через ограничение матроида. Существует два разных алгоритма, которые дают приближение , и это является оптимальным в этой модели благодаря результату Вондрака. Оба алгоритма должны вычислить функцию вида E x X f ( x ) , где X11/eExXf(x)Xэто дистрибутив с экспоненциальной поддержкой. Вычисление этой функции точно слишком дорого, но ее можно аппроксимировать выборкой, и в результате получается рандомизированный алгоритм. В отличие от этого , самый известный детерминированный алгоритм, жадный алгоритм, дает приближение.1/2

Аналогичная ситуация возникает при неограниченном субмодулярном максимизации (здесь функция не обязательно монотонна). Недавний алгоритм прорыва дает оптимальное приближение, но ее детерминированный вариант дает только 1 / 3 приближение. Здесь рандомизация проявляется либо точно так же, как в монотонном случае, либо (в другой версии алгоритма), делая несколько случайных выборов по пути.1/21/3

Один из авторов последней работы догадках , что это лучшее , что детерминированный алгоритм может достичь, и мы можем так же предположение , что +1 / +2 это лучшее , что может быть достигнуто в предыдущей задаче. Если эти предположения верны, то это вполне естественная ситуация, в которой доказуемо помогает рандомизация.1/31/2

Недавно Добзински и Вондрак показали, как преобразовать нижние границы значения оракула (для рандомизированных алгоритмов) в результаты твердости, при условии, что NP отличается от RP (ключевым ингредиентом является декодирование списка). Следует отметить, что преобразование опирается на конкретный метод, используемый для доказательства нижних оценок оракула. Возможно, это правда, что детерминистическая ценность оракула нижних границ также приводит к результатам твердости.

Юваль Фильмус
источник
Интересно, подпадает ли проблема оценки объема под эту модель «ценности оракула». В этой модели вам дается оракул членства для выпуклого объекта, объем которого вы оцениваете, и хорошо известно, что он не может быть детерминированно приближен даже к экспоненциальному коэффициенту, но может быть произвольно аппроксимирован произвольно с помощью рандомизированного алгоритма.
Суреш Венкат
12

NPUPBPPP

И тем не менее, эти сокращения различной мощности существуют. Фактически, вычислительный ресурс, такой как случайность, не обязательно имеет фиксированное количество вычислительной мощности, которое является «значительным» или «не значимым».

LPBPPBQPPPSPACENPNP

MCCM

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

NPUPPHBPPPPHBPPPP

BPP=PBPPΣ2pΔ2pNPcoNP

PHPBPPP, then you should consider the possibility that facilities such as randomness and nondeterminism can have powers which are not easily comparable to one another, and which can synergize or catalyse one another to give computational power that neither one would plausibly have on its own. The hypothesis that BPP=P is not that "randomness has no power", but that randomness alone (or rather, supplemented only by polynomial time computation and provided to an otherwise deterministic computational model) is not powerful. But this does not mean that there can be no power in randomness, which may be catalysed by other computational resources.

Niel de Beaudrap
источник
«кроме дизъюнктивного сокращения таблицы истинности», - а как насчет других монотонных сокращений таблицы истинности, таких как конъюнктивное сокращение таблицы истинности?
@RickyDemer: Quite right. At the time I wrote this, I was working on certain nondeterministic classes related to NL, for which closure under d.t.t- and c.t.t.-reductions both would have implied closure under complements, and so I omitted mention of c.t.t.; but the same is clearly not true for NL or NP themselves. I'll edit my answer.
Ниль де Бодрап,
@NieldeBeaudrap This is a very good answer as well.
Tayfun Pay