NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Содержание
Задача
в 3-КНФ,
Теорема
Доказательство
Для того, чтобы доказать NP-полноту задачи, необходимо установить следующие факты:
- .
- ;
Доказательство принадлежности 3SAT классу NP
Возьмем в качестве сертификата набор
, где . Верификатор подставляет в формулу и проверяет её на равенство единице. Время работы верификатора и длина сертификата, очевидно, полиномиальны. Итак, .Доказательство принадлежности 3SAT классу NPH
Покажем, что сводится по Куку к .
, то естьРассмотрим один дизъюнкт булевой формулы в форме 3-КНФ. Он должен иметь вид . Научимся приводить члены вида , , к нужному виду.
- заменим на . Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых ;
- заменим на - свели задачу к предыдущей;
- Если встречается дизъюнкт вида , введем новых переменных и заменим наш дизъюнкт на дизъюнкта: . Покажем, что эта замена корректна.
Для этого, сделаем утверждение:
Если
- набор значений , удовлетворяющий дизъюнкт , то существует такой набор значений , что каждый из новых дизъюнктов также удовлетворен.Действительно, среди значений
хотя бы одно должно равняться . Не умаляя общности, пусть для некоторого . Тогда, пусть для и для . Тогда, все новые дизъюнкты также будут удовлетворены.Наоборот, пусть все новые дизъюнкты удовлетворяются некоторым набором значений
и . Покажем, что тогда хотя бы один из должен равняться .Предположим, что это не так, и
. Тогда, первые дизъюнкта в удовлетворены только если . Однако, если , то последний дизъюнкт не может быть удовлетворен. Пришли к противоречию, следовательно хотя бы один из должен равняться .Таким образом, мы свели
к , следовательно . Теорема доказана.