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