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