Изменения

|definition=задача #MON-CNF (Satisfability problem for monotone boolean formulas) — --- задача вычисления количества удовлетворяющих подстановок для монотонной булевой формулы, записанной в [[КНФ]] <tex>f = \bigwedge \limits _{k=1}^n \bigvee_{i \in C_k} x_i</tex>

Karl Bringmann, Tobias Friedrich, Approximating the volume of unions and intersections of high-dimensional geometric objects, ISAAC'2008, http://www.texmpi-inf.uniyarmpg.ac.rude/~kbringma/docpaper/shulmeis2008ISAAC_Volume.pdf

Задача MON-CNF состоит в нахождении количества Количество удовлетворяющих подстановок дляфункции

 Количество ее удовлетворяющих подстановок равно меньше <tex>2^d</tex> минус на количество удовлетворяющих подстановок ее отрицания

поэтому далее будем работать с <tex>\overline{f}</tex>.Для каждого клоза конъюнкта <tex>\bigwedge_{i \in C_k} \neg x_i</tex> построим соответствующий ему гиперкуб <tex>A_k = [0,a^k_1]\times...\times[0,a^k_d]</tex>

</tex>.

напримерНапример, гиперкубу

<tex>C_1 = \{x\}</tex> будет соответствовать клоз конъюнкт <tex>\neg x_1</tex>

а <tex>C_2 = \{1,2\}</tex> клоз конъюнкт <tex>\neg x_1 \wedge \neg x_2</tex>.

Заметим, что Запишем объединение гиперкубов <tex>A_k</tex> может быть записано как объединение гиперкубов вида <tex>B_{x_1,...,x_d} = [x_1,x_1 + 1]\times ... \times [x_d, x_d + 1]</tex>, где <tex>x_i \in \{0,1\}, i \in [d]</tex>.