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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
(Определение)
Строка 4: Строка 4:
 
* Говорят, что формула записана в ''конъюнктивной нормальной форме'' (КНФ), если представляет собой логическое '''И''' дизъюнктов.
 
* Говорят, что формула записана в ''конъюнктивной нормальной форме'' (КНФ), если представляет собой логическое '''И''' дизъюнктов.
 
==== Определение ====
 
==== Определение ====
<tex>CNFSAT = \{\phi \ |\ \phi </tex> ''в КНФ,'' <tex>\phi \in </tex> [[Теорема Кука]] <tex> \} </tex> &mdash; задача о выполнимости булевой формулы в форме КНФ.
+
<tex>CNFSAT = \{\phi \ |\ \phi </tex> ''в КНФ,'' <tex>\phi \in </tex> [[SAT]] <tex> \} </tex> &mdash; задача о выполнимости булевой формулы в форме КНФ.
  
 
== Теорема ==
 
== Теорема ==

Версия 14:49, 17 марта 2010

Определения

  • Литералом является переменная или отрицание переменной. Например, [math]x[/math] или [math]\neg y[/math].
  • Дизъюнктом называется логическое ИЛИ одного или нескольких литералов. Например, [math]x \vee \neg y \vee z[/math]
  • Говорят, что формула записана в конъюнктивной нормальной форме (КНФ), если представляет собой логическое И дизъюнктов.

Определение

[math]CNFSAT = \{\phi \ |\ \phi [/math] в КНФ, [math]\phi \in [/math] SAT [math] \} [/math] — задача о выполнимости булевой формулы в форме КНФ.

Теорема

[math] CNFSAT \in NPC. [/math]

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

Для доказательства теоремы необходимо установить два факта:

  • [math] CNFSAT /in NP [/math]
  • [math] CNFSAT /in NPH [/math]