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

Теорема Валианта-Вазирани (Valiant–Vazirani theorem) является клевым современным результатом в теории сложности.

Формулировка теоремы

Если язык USAT принадлежит классу P, то классы языков NP и RP совпадают.

Доказательство теоремы

Для доказательства этого факта покажем, что по заданной в КНФ формуле [math]\phi[/math] можно за полиномиальное время построить набор формул [math]\phi_1 \ldots \phi_m[/math] такой, что:

• если формула [math]\phi[/math] неудовлетворима (то есть не принадлежит SAT), то все формулы [math]\phi_1 \ldots \phi_m[/math] также неудовлетворимы;
• если формула [math]\phi[/math] удовлетворима, то с вероятностью большей ½ в наборе найдется формула [math]\phi_i[/math] ∈ USAT.

Таким образом задача принадлежности формулы языку SAT будет разрешаться за полиномиальное с вероятностью большей ½, то есть SAT ∈ RP, следовательно, NP=RP.

Внешние ссылки

Оригинальная статья 1986 года - Valiant, Leslie G., Vijay Vazirani NP is as easy as detecting unique solutions

Лекция Э.А.Гирша