3-ВЫПОЛНИМОСТЬ (3-SAT) — задача выполнимости КНФ, каждая скобка которой содержит не более трёх литералов. Она принадлежит классу \(NP\) и является
NP-трудность доказывается сведением SAT к 3-SAT. Длинную скобку \(y_1\vee\cdots\vee y_m\), \(m>3\), заменяют двумя скобками с новой переменной \(u\): \((y_1\vee y_2\vee u)\wedge(y_3\vee\cdots\vee y_m\vee\neg u)\). Такое преобразование сохраняет выполнимость и уменьшает длину длинной скобки. Повторяя его, получают равновыполнимую 3-КНФ полиномиального
Что важно запомнить
- 3-SAT использует КНФ со скобками длины не более трёх литералов.
- Принадлежность \(NP\) проверяется так же, как для SAT: выбранный набор значений можно проверить за полиномиальное время.
- Для NP-трудности в курсе строится сведение
- Новые переменные нужны только для разбиения длинных скобок. Полученная формула должна быть равновыполнима исходной.
Почему 3-SAT принадлежит NP
Свидетельством положительного ответа служит набор значений всех переменных. Подстановка этого набора и проверка всех скобок требуют времени, полиномиального по длине записи формулы. Поэтому \(3\text{-SAT}\in NP\).
Сведение SAT к 3-SAT
Пусть в КНФ есть скобка \(C=y_1\vee\cdots\vee y_m\) с \(m>3\). Берут новую переменную \(u\), не встречающуюся в исходной формуле, и вместо \(C\) записывают
\((y_1\vee y_2\vee u)\wedge(y_3\vee\cdots\vee y_m\vee\neg u)\).
Если исходная скобка истинна за счёт \(y_1\vee y_2\), можно положить \(u=0\). Если она истинна за счёт одного из \(y_3,\ldots,y_m\), можно положить \(u=1\). Обратно, если обе новые скобки истинны, то при \(u=0\) истинна первая группа литералов, а при \(u=1\) — вторая. Значит исходная скобка тоже истинна.
Замена уменьшает число литералов в длинной скобке на единицу и добавляет лишь постоянное число новых символов. Повторяя её, каждую скобку приводят к длине не более трёх. Число шагов и размер результата полиномиальны по размеру исходной КНФ. Поэтому \(SAT\prec 3\text{-SAT}\), а вместе с принадлежностью \(NP\) это доказывает NP-полноту
Пример простыми словами
Скобку \(a\vee b\vee c\vee d\vee e\) можно сначала заменить на \((a\vee b\vee u)\wedge(c\vee d\vee e\vee\neg u)\). Во второй скобке ещё четыре литерала, поэтому вводят новую переменную \(v\): получают \((a\vee b\vee u)\wedge(c\vee d\vee v)\wedge(e\vee\neg u\vee\neg v)\). Новая 3-КНФ выполнима тогда и только тогда, когда была выполнима исходная скобка.
Частые ошибки
- Доказывать только \(3\text{-SAT}\in NP\). Для NP-полноты нужна ещё NP-трудность.
- Строить сведение в обратную сторону \(3\text{-SAT}\prec SAT\): оно очевидно, но не доказывает трудность 3-SAT.
- Требовать логической эквивалентности формул на расширенном наборе переменных. Для сведения достаточно равновыполнимости: существует удовлетворяющий набор исходных переменных тогда и только тогда, когда существует расширяющий его набор новых переменных.
