Hardprob/Maximum Renamable Horn Subformula — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Набор булевых переменных <em>U</em>, коллекция <em>C</em> ск…») |
(нет различий)
|
Версия 23:54, 13 апреля 2023
- Набор булевых переменных U, коллекция C скобок-конъюнкций не больше чем из трех литералов.
- Найти переименовываемую хорнову подформулу C' от C, т.е. подмножество C'⊆ C, т.к. здесь существует подмножество , таких переменных, что перестановка литералов в делает C' хорновой булевой формулы, где .
- Максимизировать размер подформулы, т.е. |C'|.
Задача в лаб22 (рид-онли просмотр)