Теорема Валианта – Вазирани

Теорема Валианта -Вазирани — это теорема теории сложности вычислений, утверждающая, что если существует алгоритм с полиномиальным временем для Unambiguous-SAT , то NP = RP . Это доказали Лесли Валиант и Виджай Вазирани в своей статье под названием «NP так же просто, как обнаружить уникальные решения», опубликованной в 1986 году.

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

Схема доказательства

Однозначный SAT — это проблема обещания , позволяющая решить, является ли данная булева формула, имеющая не более одного удовлетворяющего назначения, невыполнимой или имеет ровно одно удовлетворяющее присвоение. В первом случае алгоритм Unambiguous-SAT должен отклонить, а во втором — принять формулу.Если формула имеет более одного удовлетворяющего назначения, то никаких условий на поведение алгоритма не существует.Проблема обещаний Unambiguous-SAT может быть решена с помощью недетерминированной машины Тьюринга , которая имеет не более одного принимающего пути вычислений, поэтому она принадлежит к обещанной версии класса сложности UP (класс UP как таковой определен только для языков).

Доказательство теоремы Валианта-Вазирани состоит из вероятностной редукции, которая по формуле F с n переменными выводит последовательность формул G ₀ ,..., G _n такую, что:

• Каждое удовлетворяющее присваивание любого G _i также удовлетворяет F . Таким образом, если F невыполнимо, то все G _i , i ⩽ n , невыполнимы.
• Если F выполнимо, то с вероятностью не менее 1/4 некоторый G _i имеет единственное удовлетворяющее назначение.

Идея редукции состоит в последовательном пересечении пространства решений формулы F n случайными линейными гиперплоскостями в $\mathbb {F} _{2}^{n}$.

Как следствие (не необходимое для аргумента NP = RP , но представляющее независимый интерес), если мы выберем один из G _i наугад, мы получим рандомизированное сокращение с односторонней ошибкой от SAT до Unambiguous-SAT, которое с вероятностью будет успешным. не менее Ω(1/ n ). То есть, если F невыполнима, выходная формула всегда невыполнима, а если F выполнима, то выходная формула имеет единственное удовлетворяющее назначение с вероятностью Ω(1/ n ).

Теперь, предполагая, что Unambiguous-SAT разрешима с помощью алгоритма A с полиномиальным временем , мы получаем алгоритм RP для SAT, запуская A на G _i для каждого i ≤ n . Если F невыполнимо, то A отвергает все Gi _как невыполнимые, тогда как если F выполнимо, то A некоторые Gi _{принимает} с вероятностью не менее 1/4. (Мы можем улучшить вероятность принятия, повторив сокращение несколько раз.)

В более общем плане этот аргумент безоговорочно показывает, что NP включен в RP. ^{обещаниеUP} .

Альтернативное доказательство основано на лемме об изоляции Малмули, Вазирани и Вазирани. Они рассматривают более общую настройку, и применительно к данной настройке это дает вероятность изоляции всего лишь $\Omega (1/n^{8})$.