NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ — различия между версиями
(→Доказательство принадлежности 3SAT классу NPH) |
(→Доказательство принадлежности 3SAT классу NPH) |
||
(не показано 8 промежуточных версий 2 участников) | |||
Строка 27: | Строка 27: | ||
* Если встречается дизъюнкт вида <tex>(x_1 \ldots x_k), k \ge 3</tex>, введем <tex>k-3</tex> новых переменных и заменим наш дизъюнкт на <tex>k-2</tex> дизъюнкта: <tex>(x_1 \vee x_2 \vee z_1) \wedge (x_3 \vee \neg z_1 \vee z_2) \wedge (x_4 \vee \neg z_2 \vee z_3) \wedge \ldots \wedge (x_{k-1} \vee x_k \vee \neg z_{k-3})</tex>. Покажем, что эта замена корректна. | * Если встречается дизъюнкт вида <tex>(x_1 \ldots x_k), k \ge 3</tex>, введем <tex>k-3</tex> новых переменных и заменим наш дизъюнкт на <tex>k-2</tex> дизъюнкта: <tex>(x_1 \vee x_2 \vee z_1) \wedge (x_3 \vee \neg z_1 \vee z_2) \wedge (x_4 \vee \neg z_2 \vee z_3) \wedge \ldots \wedge (x_{k-1} \vee x_k \vee \neg z_{k-3})</tex>. Покажем, что эта замена корректна. | ||
− | Для этого, сделаем | + | Для этого, сделаем утверждение: |
− | |||
− | + | Если <tex>(x_{1}^* \ldots x_{k}^*)</tex> - набор значений <tex>x_i</tex>, удовлетворяющий дизъюнкт <tex>(x_1 \vee \ldots \vee x_k)</tex>, то существует такой набор значений <tex>z_{1}^* \ldots z_{k-3}^*</tex>, что каждый из <tex>k-2</tex> новых дизъюнктов также удовлетворен. | |
− | + | Действительно, среди значений <tex>(x_{1}^* \ldots x_{k}^*)</tex> хотя бы одно должно равняться <tex>true</tex>. Не умаляя общности, пусть для некоторого <tex>r: 1 \le r \le k, x_r = true</tex>. Тогда, пусть <tex>z_{s}^*=true</tex> для <tex>s \le r-2</tex> и <tex>z_{s}^*=false</tex> для <tex>s > r - 2</tex>. Тогда, все новые дизъюнкты также будут удовлетворены. | |
− | Предположим, что это не так, и <tex>x_i = false, | + | Наоборот, пусть все новые дизъюнкты удовлетворяются некоторым набором значений <tex>x_i</tex> и <tex>z_i</tex>. Покажем, что тогда хотя бы один из <tex>x_i</tex> должен равняться <tex>true</tex>. |
+ | |||
+ | Предположим, что это не так, и <tex>x_i = false, i = 1..k</tex>. Тогда, первые <tex>k-3</tex> дизъюнкта в <tex>3SAT</tex> удовлетворены только если <tex>z_i = true, i=1..k-3</tex>. Однако, если <tex>z_{k-3}=true</tex>, то последний дизъюнкт <tex>(x_{k-1} \vee x_k \vee \neg z_{k-3})</tex> не может быть удовлетворен. Пришли к противоречию, следовательно хотя бы один из <tex>x_i</tex> должен равняться <tex>true</tex>. | ||
Таким образом, мы свели <tex>CNFSAT</tex> к <tex>3SAT</TEX>, следовательно <tex>3SAT \in NPH</tex>. Теорема доказана. | Таким образом, мы свели <tex>CNFSAT</tex> к <tex>3SAT</TEX>, следовательно <tex>3SAT \in NPH</tex>. Теорема доказана. |
Версия 20:13, 19 марта 2010
Содержание
Задача
в 3-КНФ,
Теорема
Доказательство
Для того, чтобы доказать NP-полноту задачи, необходимо установить следующие факты:
- .
- ;
Доказательство принадлежности 3SAT классу NP
Возьмем в качестве сертификата набор
, где . Верификатор подставляет в формулу и проверяет её на равенство единице. Время работы верификатора и длина сертификата, очевидно, полиномиальны. Итак, .Доказательство принадлежности 3SAT классу NPH
Покажем, что сводится по Куку к .
, то естьРассмотрим один дизъюнкт булевой формулы в форме 3-КНФ. Он должен иметь вид . Научимся приводить члены вида , , к нужному виду.
- заменим на . Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых ;
- заменим на - свели задачу к предыдущей;
- Если встречается дизъюнкт вида , введем новых переменных и заменим наш дизъюнкт на дизъюнкта: . Покажем, что эта замена корректна.
Для этого, сделаем утверждение:
Если
- набор значений , удовлетворяющий дизъюнкт , то существует такой набор значений , что каждый из новых дизъюнктов также удовлетворен.Действительно, среди значений
хотя бы одно должно равняться . Не умаляя общности, пусть для некоторого . Тогда, пусть для и для . Тогда, все новые дизъюнкты также будут удовлетворены.Наоборот, пусть все новые дизъюнкты удовлетворяются некоторым набором значений
и . Покажем, что тогда хотя бы один из должен равняться .Предположим, что это не так, и
. Тогда, первые дизъюнкта в удовлетворены только если . Однако, если , то последний дизъюнкт не может быть удовлетворен. Пришли к противоречию, следовательно хотя бы один из должен равняться .Таким образом, мы свели
к , следовательно . Теорема доказана.