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

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

Версия 23:02, 15 марта 2010

Теорема [math]3SAT \in NPC [/math], т.е. задача о выполнимости булевой формулы в форме 3-КНФ [math]NP[/math]-полна. Доказательство Для того, чтобы доказать [math]NP[/math]-полноту задачи, необходимо установить следующие факты:

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