Hardprob/Maximum Not-All-Equal 3-Satisfiability — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Множество переменных <em>U</em>, * Коллекция <em>C</em> скоб…») |
StasFomin (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
* Коллекция <em>C</em> скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше <em>3</em>. | * Коллекция <em>C</em> скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше <em>3</em>. | ||
* Найти истинное присваивание для <em>U</em>, и подмножество скобок <em>C'⊆ C</em>, таких что каждая скобка имеет по крайней мере один истинный литерал и не меньше одного ложного литерала. | * Найти истинное присваивание для <em>U</em>, и подмножество скобок <em>C'⊆ C</em>, таких что каждая скобка имеет по крайней мере один истинный литерал и не меньше одного ложного литерала. | ||
| − | * Максимизировать размер этого подмножества < | + | * Максимизировать размер этого подмножества <em>|C'| → max</em> |
---- | ---- | ||
Текущая версия на 06:51, 17 апреля 2023
- Множество переменных U,
- Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше 3.
- Найти истинное присваивание для U, и подмножество скобок C'⊆ C, таких что каждая скобка имеет по крайней мере один истинный литерал и не меньше одного ложного литерала.
- Максимизировать размер этого подмножества |C'| → max
Задача в лаб22 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «LO3»