NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ — различия между версиями
Строка 11: | Строка 11: | ||
Установим сначала первый факт, то есть <tex>NP</tex>-трудность <tex>3SAT</tex>. | Установим сначала первый факт, то есть <tex>NP</tex>-трудность <tex>3SAT</tex>. | ||
Для этого покажем, что <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>. | ||
+ | Научимся приводить члены вида <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> - свели задачу к предыдущей; |
Версия 23:39, 15 марта 2010
Теорема
, т.е. задача о выполнимости булевой формулы в форме 3-КНФ -полна.
Доказательство
Для того, чтобы доказать
-полноту задачи, необходимо установить следующие факты:- ;
- .
Установим сначала первый факт, то есть
-трудность . Для этого покажем, что , то есть сводится по Куку к .Рассмотрим один член булевой формулы в форме КНФ (скобку). В форме 3-КНФ этот член должен иметь вид
. Научимся приводить члены вида , , к нужному виду.- заменим на . Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых ;
- заменим на - свели задачу к предыдущей;