Hardprob/Maximum Renamable Horn Subformula

Ссылки сюда (2) →

• Набор булевых переменных U, коллекция C скобок-конъюнкций не больше чем из трех литералов.
• Найти переименовываемую хорнову подформулу C' от C, т.е. подмножество C'⊆ C, т.к. здесь существует подмножество S ⊆ U, таких переменных, что перестановка литералов в делает C' хорновой булевой формулы, где .
• Максимизировать размер подформулы, т.е. |C'|.

---

Код в «maximum-renamable-horn-subformula.ipynb» на гитлаб или живьем в лабе

---

• Задача в базе NP-полных задач Вигго Кана

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.