NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Теорема''' 3<tex>-SAT \in NPC </tex> (задача о выполнимости булевой формулы в форме 3-КНФ <tex>NP</tex>-полн…»)
 
(Доказательство принадлежности 3SAT классу NPH)
(не показано 38 промежуточных версий 3 участников)
Строка 1: Строка 1:
'''Теорема''' 3<tex>-SAT \in NPC </tex> (задача о выполнимости булевой формулы в форме 3-КНФ <tex>NP</tex>-полна)
+
==Задача <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 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 \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_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>. Теорема доказана.

Версия 20:13, 19 марта 2010

Задача [math]3SAT[/math]

[math]3SAT=3CNFSAT=\{\phi|\phi[/math] в 3-КНФ, [math]\phi \in SAT\}[/math]

Теорема

[math]3SAT \in NPC [/math]

Доказательство

Для того, чтобы доказать NP-полноту задачи, необходимо установить следующие факты:

  1. [math] 3SAT \in NP [/math].
  2. [math] 3SAT \in NPH [/math];

Доказательство принадлежности 3SAT классу NP

Возьмем в качестве сертификата набор [math]x_1 \ldots x_{n}[/math], где [math]x_i \in \{0,1\}[/math]. Верификатор подставляет [math]x_1 \ldots x_n[/math] в формулу и проверяет её на равенство единице. Время работы верификатора и длина сертификата, очевидно, полиномиальны. Итак, [math]3SAT \in NP[/math].

Доказательство принадлежности 3SAT классу NPH

Покажем, что [math]CNFSAT \le 3SAT[/math], то есть [math]CNFSAT[/math] сводится по Куку к [math]3SAT[/math].

Рассмотрим один дизъюнкт булевой формулы в форме 3-КНФ. Он должен иметь вид [math](x \vee y \vee z)[/math]. Научимся приводить члены вида [math](x)[/math], [math](x \vee y)[/math], [math](x_1 \vee x_{2} \vee \ldots \vee x_{m})[/math] к нужному виду.

  • [math](x \vee y)[/math] заменим на [math](x \vee y \vee z) \wedge (x \vee y \vee \neg z)[/math]. Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых [math]z[/math];
  • [math](x)[/math] заменим на [math](x \vee y) \wedge (x \vee \neg y)[/math] - свели задачу к предыдущей;
  • Если встречается дизъюнкт вида [math](x_1 \ldots x_k), k \ge 3[/math], введем [math]k-3[/math] новых переменных и заменим наш дизъюнкт на [math]k-2[/math] дизъюнкта: [math](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})[/math]. Покажем, что эта замена корректна.

Для этого, сделаем утверждение:

Если [math](x_{1}^* \ldots x_{k}^*)[/math] - набор значений [math]x_i[/math], удовлетворяющий дизъюнкт [math](x_1 \vee \ldots \vee x_k)[/math], то существует такой набор значений [math]z_{1}^* \ldots z_{k-3}^*[/math], что каждый из [math]k-2[/math] новых дизъюнктов также удовлетворен.

Действительно, среди значений [math](x_{1}^* \ldots x_{k}^*)[/math] хотя бы одно должно равняться [math]true[/math]. Не умаляя общности, пусть для некоторого [math]r: 1 \le r \le k, x_r = true[/math]. Тогда, пусть [math]z_{s}^*=true[/math] для [math]s \le r-2[/math] и [math]z_{s}^*=false[/math] для [math]s \gt r - 2[/math]. Тогда, все новые дизъюнкты также будут удовлетворены.

Наоборот, пусть все новые дизъюнкты удовлетворяются некоторым набором значений [math]x_i[/math] и [math]z_i[/math]. Покажем, что тогда хотя бы один из [math]x_i[/math] должен равняться [math]true[/math].

Предположим, что это не так, и [math]x_i = false, i = 1..k[/math]. Тогда, первые [math]k-3[/math] дизъюнкта в [math]3SAT[/math] удовлетворены только если [math]z_i = true, i=1..k-3[/math]. Однако, если [math]z_{k-3}=true[/math], то последний дизъюнкт [math](x_{k-1} \vee x_k \vee \neg z_{k-3})[/math] не может быть удовлетворен. Пришли к противоречию, следовательно хотя бы один из [math]x_i[/math] должен равняться [math]true[/math].

Таким образом, мы свели [math]CNFSAT[/math] к [math]3SAT[/math], следовательно [math]3SAT \in NPH[/math]. Теорема доказана.