Дерандомизировать Валиант-Вазирани?

29

Теорема Валианта-Вазирани говорит, что если существует алгоритм полиномиального времени (детерминированный или рандомизированный) для разграничения между формулой SAT, которая имеет ровно одно удовлетворяющее назначение, и формулой неудовлетворительного типа, - тогда NP = RP . Эта теорема доказана тем, что UNIQUE-SAT является NP- трудным при рандомизированных редукциях.

С учетом вероятных гипотез дерандомизации, теорема может быть усилена до «эффективного решения UNIQUE-SAT подразумевает NP = P ».

Моим первым инстинктом было думать, что подразумевается, что существует детерминированное сокращение с 3SAT до UNIQUE-SAT, но мне не ясно, как это конкретное сокращение может быть дерандомизировано.

Мой вопрос: что считают или знают о «дерандомизирующих сокращениях»? Это возможно? Как насчет в случае ВВ?

Поскольку UNIQUE-SAT завершен для PromiseNP при рандомизированных сокращениях, можем ли мы использовать инструмент дерандомизации, чтобы показать, что «детерминированное полиномиальное временное решение UNIQUE-SAT подразумевает, что PromiseNP = PromiseP ?

cc.complexity-theory reductions derandomization unique-solution Генри Юн
источник

4

Что касается последнего абзаца, PromiseP = PromiseNP эквивалентно P = NP.

Цуёси Ито

31

При правильных допущениях по дерандомизации (см. Klivans-van Melkebeek ) вы получите следующее: Существует вычисляемое с помощью множителя st для всех , $f(\phi)=(\psi_1,\ldots,\psi_k)$ $\phi$

Если выполнимо, то хотя бы один из имеет ровно одно удовлетворяющее присваивание. $\phi$ $\psi_i$
Если не выполнимо, то все неудовлетворительны. $\phi$ $\psi_i$

Вам понадобится k полиномов, тогда длина . Вероятно, не может быть сделано для . $\phi$ $k=1$

Лэнс Фортноу
источник

@LanceFortnow означает, что

означает, что лемма о выделении Вазирани-Валианта может быть дерандомизирована, и, таким образом,

означает детерминированное уменьшение до

что даст

?

P = B P P

$P=BPP$

P = B P P

$P=BPP$

S A T

$SAT$

P = N P

$P=NP$

Т ....

1

Нет. Вам нужно более сильное предположение, чем P = BPP, чтобы дерандомизировать Valiant-Vazirani (снова я отсылаю вас к Klivans-van Melkebeek). Даже если вы дерандомизируете Valiant-Vaizarni, это даст только результат, о котором я упоминал выше - вы не получите P = NP, если у вас не было алгоритма, который мог бы решить проблему удовлетворенности с помощью уникальных свидетелей.

Лэнс Фортноу

@LanceFortnow Просто чтобы быть ясно. Можем ли мы получить

просто

или важно, чтобы (с имеющимся у нас уровнем знаний), вероятно, нам нужно было бы дерандомизировать VV, чтобы добраться до

(это немного другой запрос, чем вопрос о том, просто ли P = BPP дает детерминированное сокращение SAT, поскольку, возможно, вообще не нужно, чтобы VV вообще требовался для получения NP в BPP ^ {oplus P }).

P^{\oplus P} = B P P^{\oplus P}

$P^{\oplus P}=BPP^{\oplus P}$

P = B P P

$P=BPP$

P^{\oplus P} = B P P^{\oplus P}

$P^{\oplus P}=BPP^{\oplus P}$

Т ....

22

Просто для справки, я наткнулся сегодня на этот действительно интересный документ, который свидетельствует о том, что детерминированное сокращение маловероятно:

Dell, H., Кабанец В., Ватанабе О. и Ван Мелкебек Д. (2012). Является ли лемма Валиант-Вазирани изолируемой? ECCC TR11-151

Они утверждают, что это невозможно, если NP не содержится в P / poly.

Генри Юн
источник

Дерандомизировать Валиант-Вазирани?

Ответы: