Изменения
Нет описания правки
== Используемые обозначения ==
|definition=
Задача #MON-CNF – задача нахождения числа удовлетворяющих подстановок для монотонной булевой формулыфункции, записанной в КНФ, <tex>f = \bigwedge \limits_{k=1}^n \bigvee \limits_{i \in C_k} x_i</tex>,
где клозы <tex> C_k \subseteq {\{1,...,d\}}</tex>.
За <tex>\Box(a_1, \ldots, a_d)</tex> будем обозначать прямоугольный гиперпараллелепипед <tex>[0, a_1] \times \ldots \times [0, a_d]</tex>.
Пусть <tex>f = \bigwedge \limits_{k=1}^n \bigvee \limits_{i \in C_k} x_i</tex> – монотонная булева формула функция в КНФ, <tex> C_k \subseteq {\{1,...,d\}}</tex>.
Построим параллелепипеды <tex>A_k = \Box(a_1^k, \ldots, a_d^k, 2^d + 2) \subseteq \mathbb{R}^{d+1}</tex> для каждого клоза формулы, при этом
}}
