NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 32 промежуточные версии 4 участников) | |||
Строка 1: | Строка 1: | ||
− | + | ==Задача <tex>3SAT</tex>== | |
+ | <tex>3SAT=3CNFSAT=\{\phi|\phi</tex> в 3-КНФ, <tex>\phi \in SAT\}</tex> | ||
− | + | ==Теорема== | |
− | + | <tex>3SAT \in NPC </tex> | |
− | Для того, чтобы доказать | + | ==Доказательство== |
+ | |||
+ | Для того, чтобы доказать [[Понятие_NP-трудной_и_NP-полной_задачи|NP-полноту]] задачи, необходимо установить следующие факты: | ||
# <tex> 3SAT \in NP </tex>. | # <tex> 3SAT \in NP </tex>. | ||
# <tex> 3SAT \in NPH </tex>; | # <tex> 3SAT \in NPH </tex>; | ||
+ | ===Доказательство принадлежности 3SAT классу NP=== | ||
+ | Возьмем в качестве сертификата набор <tex>x_1 \ldots x_{n}</tex>, где <tex>x_i \in \{0,1\}</tex>. | ||
+ | Верификатор подставляет <tex>x_1 \ldots x_n</tex> в формулу и проверяет её на равенство единице. | ||
+ | Время работы верификатора и длина сертификата, очевидно, полиномиальны. Итак, <tex>3SAT \in NP</tex>. | ||
− | + | ===Доказательство принадлежности 3SAT классу NPH=== | |
− | + | Покажем, что <tex>CNFSAT \le 3SAT</tex>, то есть <tex>CNFSAT</tex> [[Сведение_по_Куку|сводится по Куку]] к <tex>3SAT</tex>. | |
− | |||
− | |||
− | Рассмотрим один | + | Рассмотрим один [[NP-полнота_задачи_о_выполнимости_булевой_формулы_в_форме_КНФ|дизъюнкт булевой формулы]] в форме 3-КНФ. Он должен иметь вид <tex>(x \vee y \vee z)</tex>. |
Научимся приводить члены вида <tex>(x)</tex>, <tex>(x \vee y)</tex>, <tex>(x_1 \vee x_{2} \vee \ldots \vee x_{m})</tex> к нужному виду. | Научимся приводить члены вида <tex>(x)</tex>, <tex>(x \vee y)</tex>, <tex>(x_1 \vee x_{2} \vee \ldots \vee x_{m})</tex> к нужному виду. | ||
* <tex>(x \vee y)</tex> заменим на <tex>(x \vee y \vee z) \wedge (x \vee y \vee \neg z)</tex>. Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых <tex>z</tex>; | * <tex>(x \vee y)</tex> заменим на <tex>(x \vee y \vee z) \wedge (x \vee y \vee \neg z)</tex>. Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых <tex>z</tex>; | ||
* <tex>(x)</tex> заменим на <tex>(x \vee y) \wedge (x \vee \neg y)</tex> - свели задачу к предыдущей; | * <tex>(x)</tex> заменим на <tex>(x \vee y) \wedge (x \vee \neg y)</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</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>. Теорема доказана. | ||
− | + | [[Категория:NP]] |
Текущая версия на 19:38, 4 сентября 2022
Содержание
Задача
в 3-КНФ,
Теорема
Доказательство
Для того, чтобы доказать NP-полноту задачи, необходимо установить следующие факты:
- .
- ;
Доказательство принадлежности 3SAT классу NP
Возьмем в качестве сертификата набор
, где . Верификатор подставляет в формулу и проверяет её на равенство единице. Время работы верификатора и длина сертификата, очевидно, полиномиальны. Итак, .Доказательство принадлежности 3SAT классу NPH
Покажем, что сводится по Куку к .
, то естьРассмотрим один дизъюнкт булевой формулы в форме 3-КНФ. Он должен иметь вид . Научимся приводить члены вида , , к нужному виду.
- заменим на . Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых ;
- заменим на - свели задачу к предыдущей;
- Если встречается дизъюнкт вида , введем новых переменных и заменим наш дизъюнкт на дизъюнкта: . Покажем, что эта замена корректна.
Для этого, сделаем утверждение:
Если
- набор значений , удовлетворяющий дизъюнкт , то существует такой набор значений , что каждый из новых дизъюнктов также удовлетворен.Действительно, среди значений
хотя бы одно должно равняться . Не умаляя общности, пусть для некоторого . Тогда, пусть для и для . Тогда, все новые дизъюнкты также будут удовлетворены.Наоборот, пусть все новые дизъюнкты удовлетворяются некоторым набором значений
и . Покажем, что тогда хотя бы один из должен равняться .Предположим, что это не так, и
. Тогда, первые дизъюнкта в удовлетворены только если . Однако, если , то последний дизъюнкт не может быть удовлетворен. Пришли к противоречию, следовательно хотя бы один из должен равняться .Таким образом, мы свели
к , следовательно . Теорема доказана.