Изменения

Перейти к: навигация, поиск

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

176 байт добавлено, 17:26, 16 марта 2010
Нет описания правки
Для того, чтобы доказать <tex>NP</tex>-полноту задачи, необходимо установить следующие факты:
# <tex> 3SAT \in NP </tex>.
# <tex> 3SAT \in NPH </tex>;
# <tex> 3SAT \in NP </tex>.
Установим сначала первый факт----# Для того, то есть чтобы доказать, что <tex>3SAT \in NP </tex>, предъявим сертификат: набор <tex>x_1 \ldots x_{n}</tex>, удовлетворяющий формулу. ----Теперь докажем <tex>NP</tex>-трудность <tex>3SAT</tex>.
Для этого покажем, что <tex>CNFSAT \le 3SAT</tex>, то есть <tex>CNFSAT</tex> сводится по Куку к <tex>3SAT</tex>.
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/264»

Навигация