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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
(Доказательство принадлежности 3SAT классу NPH)
Строка 20: Строка 20:
 
Покажем, что <tex>CNFSAT \le 3SAT</tex>, то есть <tex>CNFSAT</tex> [[Сведение_по_Куку|сводится по Куку]] к <tex>3SAT</tex>.
 
Покажем, что <tex>CNFSAT \le 3SAT</tex>, то есть <tex>CNFSAT</tex> [[Сведение_по_Куку|сводится по Куку]] к <tex>3SAT</tex>.
  
Рассмотрим один дизъюнкт булевой формулы в форме 3-КНФ. Он должен иметь вид <tex>(x \vee y \vee z)</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> к нужному виду.
  

Версия 18:25, 17 марта 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]CNFSAT[/math] к [math]3SAT[/math], следовательно [math]3SAT \in NPH[/math]. Теорема доказана.