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

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

Версия 23:07, 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].

Установим сначала первый факт, то есть [math]NP[/math]-трудность [math]3SAT[/math]. Для этого покажем, что [math]CNFSAT \le 3SAT[/math], то есть [math]CNFSAT[/math] сводится по Куку к [math]3SAT[/math].