Введение
Если существует алгоритм полиномиального времени для однозначного SAT, то NP = RP. Теорема Валианта — Вазирани — это теорема в теории вычислительной сложности, утверждающая, что если существует алгоритм полиномиального времени для однозначного SAT, то NP = RP. Она была доказана Лесли Валиантом и Виджаем Вазирани в их статье под названием «NP так же легко, как обнаружение единственных решений», опубликованной в 1986 году. Теорема Валианта — Вазирани подразумевает, что задача булевой выполнимости, являющаяся NP-полной, остаётся вычислительно сложной задачей, даже если гарантируется, что входные экземпляры имеют не более одного выполнимого назначения.
The Valiant–Vazirani theorem is a theorem in computational complexity theory stating that if there is a polynomial time algorithm for Unambiguous SAT, then NP = RP. It was proven by Leslie Valiant and Vijay Vazirani in their paper titled NP is as easy as detecting unique solutions published in 1986. The Valiant–Vazirani theorem implies that the Boolean satisfiability problem, which is NP complete, remains a computationally hard problem even if the input instances are promised to have at most one satisfying assignment.
Конспект доказательства
Неоднозначная SAT – это задача обещания, заключающаяся в определении, является ли данная булева формула, имеющая не более одного удовлетворяющего назначения, выполнимой или имеет ровно одно удовлетворяющее назначение. В первом случае алгоритм для неоднозначной SAT должен отклонять формулу, а во втором – принимать. Если формула имеет более одного удовлетворяющего назначения, то никаких ограничений на поведение алгоритма нет. Задача обещания Unambiguous SAT может быть решена недетерминированной машиной Тьюринга, имеющей не более одного принимающего пути вычисления, следовательно, она принадлежит к версии обещания класса сложности UP (класс UP как таковой определен только для языков). Доказательство теоремы Валианта – Вазирани состоит из вероятностного сведения, которое, получив формулу F с n переменными, выдает последовательность формул G0, …, Gn таким образом, что: любое удовлетворяющее назначение для любой Gi также удовлетворяет F. Таким образом, если F невыполнима, то все Gi, i ≤ n, невыполнимы. Если F выполнима, то с вероятностью не менее 1/4, некоторая Gi имеет единственное удовлетворяющее назначение. Идея сведения состоит в последовательном пересечении пространства решений формулы F с n случайными линейными гиперплоскостями в пространстве. Как следствие (не требуется для аргумента NP = RP, но представляет самостоятельный интерес), если мы случайно выберем одну из формул Gi, мы получим рандомизированное сведение с односторонней ошибкой от SAT к Unambiguous SAT, которое успешно работает с вероятностью не менее Ω(1/n). То есть, если F невыполнима, выходная формула всегда невыполнима, а если F выполнима, то выходная формула имеет единственное удовлетворяющее назначение с вероятностью Ω(1/n). Теперь, предполагая, что Unambiguous SAT разрешима алгоритмом за полиномиальное время A, мы получим алгоритм RP для SAT, запустив A на Gi для каждого i ≤ n. Если F невыполнима, то A отклонит все Gi, поскольку они невыполнимы, в то время как если F выполнима, то A примет некоторую Gi с вероятностью не менее 1/4. (Мы можем улучшить вероятность принятия, повторив сведение несколько раз.) В более общем плане, этот аргумент безусловно показывает, что NP содержится в RPpromiseUP. Альтернативное доказательство основано на лемме об изоляции, предложенной Mulmuley, Vazirani и Vazirani. Они рассматривают более общую постановку задачи, и применительно к данной постановке это дает вероятность изоляции, равную лишь .
Every satisfying assignment of any Gi also satisfies F. Thus, if F is unsatisfiable, then all Gi, i ≤ n, are unsatisfiable. If F is satisfiable, then with probability at least 1/4, some Gi has a unique satisfying assignment. The idea of the reduction is to successively intersect the solution space of the formula F with n random linear hyperplanes in
As a consequence (not needed for the NP = RP argument, but of independent interest), if we choose one of the Gi at random, we obtain a randomized reduction with one sided error from SAT to Unambiguous SAT that succeeds with probability at least Ω(1/n). That is, if F is unsatisfiable, the output formula is always unsatisfiable, and if F is satisfiable, then the output formula has a unique satisfying assignment with probability Ω(1/n). Now, assuming Unambiguous SAT is solvable by a polynomial time algorithm A, we obtain an RP algorithm for SAT by running A on Gi for each i ≤ n. If F is unsatisfiable, then A rejects all Gi as they are unsatisfiable, whereas if F is satisfiable, then A accepts some Gi with probability at least 1/4. (We can improve the acceptance probability by repeating the reduction several times.) More generally, this argument shows unconditionally that NP is included in RPpromiseUP. An alternative proof is based on the isolation lemma by Mulmuley, Vazirani, and Vazirani. They consider a more general setting, and applied to the setting here this gives an isolation probability of only .