4628
правок
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Перейти к навигации
Перейти к поиску
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 03:54, 25 марта 2025
, 25 март→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
MAX 2-SAT представляет собой классическую задачу оптимизации. Гэйри, Джонсоном и Стокмайером [ ] было показано, что ее версия с принятием решений (decision version) является NP-полной, что резко отличает ее от задачи 2-КНФ (2-ВЫП), которая решается за линейное время [ ]. Чтобы получить представление о сложности проблемы, приведем краткое описание NP-полноты. Можно преобразовать любой экземпляр задачи 3-КНФ F в MAX-экземпляр 2-КНФ | MAX 2-SAT представляет собой классическую задачу оптимизации. Гэйри, Джонсоном и Стокмайером [7] было показано, что ее версия с принятием решений (decision version) является NP-полной, что резко отличает ее от задачи 2-КНФ (2-ВЫП), которая решается за линейное время [2]. Чтобы получить представление о сложности проблемы, приведем краткое описание NP-полноты. Можно преобразовать любой экземпляр задачи 3-КНФ F в MAX-экземпляр 2-КНФ F', заменив каждый дизъюнкт F, такой, что: | ||
где | <math>c_i = ( \ell_1 \lor \ell_2 \lor \ell_2)</math>, где <math>\ell_1, \ell_2</math> и <math>\ell_3</math> – произвольные литералы, коллекцией дизъюнктов в 2-КНФ | ||
<math>(\ell_1), (\ell_2), (\ell_3), (c_i), (\lnot \ell_1 \lor \lnot \ell_2), (\lnot \ell_2 \lor \lnot \ell_3), (\lnot \ell_1 \lor \lnot \ell_3), (\ell_1 \lor c_i), (\ell_2 \lor c_i), (\ell_3 \lor c_i)</math> | |||
где <math>c_i</math> – новая переменная. Верны следующие утверждения: | |||
• Если присваивание делает | • Если присваивание делает <math>c_i</math> выполнимой, то из десяти дизъюнктов коллекции 2-КНФ могут быть выполнимыми ровно семь. | ||
• Если присваивание делает <math>c_i</math> невыполнимой, то ровно шесть из десяти дизъюнктов коллекции 2-КНФ могут быть выполнимыми. | |||
Если F выполнима, то существует присваивание, делающее выполнимыми 7/10 дизъюнктов в | |||
Если F выполнима, то существует присваивание, делающее выполнимыми 7/10 дизъюнктов в F', в противном случае никакое присваивание не делает выполнимыми более чем 7/10 дизъюнктов в F'. Поскольку задача 3-ВЫП сводится к МАКС 2-ВЫП, из этого следует, что МАКС 2-ВЫП (как задача с принятием решений) NP-полна. | |||
== Нотация == | == Нотация == | ||