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

Если существует полиномиальный алгоритм для однозначного SAT, то NP равно RP

Теорема Вэлианта–Вазирани — это теорема в теории сложности вычислений, утверждающая, что если существует полиномиальный алгоритм для Unambiguous-SAT , то NP = RP . Это было доказано Лесли Вэлиант и Виджаем Вазирани в их статье под названием NP is as easy as detect unique solutions, опубликованной в 1986 году. ^[1]

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

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

Unambiguous-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 отвергает все G _i , поскольку они невыполнимы, тогда как если F выполнима, то A принимает некоторые G _i с вероятностью не менее 1/4. (Мы можем улучшить вероятность принятия, повторив сокращение несколько раз.)

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

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

Ссылки

^ Валиант, Л.; Вазирани, В. (1986). «NP так же просто, как обнаружение уникальных решений» (PDF) . Теоретическая информатика . 47 : 85– 93. doi : 10.1016/0304-3975(86)90135-0 .

[1] Валиант, Л.; Вазирани, В. (1986). «NP так же просто, как обнаружение уникальных решений» (PDF) . Теоретическая информатика . 47 : 85– 93. doi : 10.1016/0304-3975(86)90135-0 .