Изменения

Перейти к: навигация, поиск

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

732 байта добавлено, 12:40, 3 мая 2010
Нет описания правки
===Доказательство теоремы===
Для доказательства этого факта покажем, что по заданной в КНФ формуле <tex>\phi</tex> можно за полиномиальное время построить набор формул <tex>\phi_1 \ldots \phi_m</tex> такой, что:
* если формула <tex>\phi</tex> неудовлетворима (то есть не принадлежит '''[[SAT]]'''), то все формулы <tex>\phi_1 \ldots \phi_m</tex> также неудовлетворимы;
* если формула <tex>\phi</tex> удовлетворима, то с вероятностью большей ½ в наборе найдется формула <tex>\phi_i</tex> ∈ '''USAT'''.
==Внешние ссылки==
165
правок

Навигация