1632
правки
Изменения
м
rollbackEdits.php mass rollback
== #P-трудность задачи вычисления гиперобъема ==
{{Определение
|definition=Задача #MON-CNF (Satisfability problem for monotone boolean formulas) — задача вычисления количества удовлетворяющих подстановок для монотонной булевой формулы, записанной в [[КНФ]] <tex>f = \bigwedge \limits _{k=1}^n \bigvee_{i \in C_k} x_i</tex>,
где все дизъюнкты <tex> C_k \subseteq {1,...,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>A = \bigcup \limits _{k=1}^n A_k</tex>. Заметим, что так как все вершины гиперкубов гиперпараллелепипедов <tex>A_i</tex> лежат в точках с целочисленными координатами 0,1 или 2, то и <tex>A</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> (то есть на гиперкубики гиперкубы со сторонами 1 с координатами ближайшей к началу координат вершины 0 или 1).
Более того, из-за целочисленности вершин <tex>A_i</tex>, каждый из этих гиперкубиков гиперкубов лежит в хотя бы одном из <tex>A_i</tex>
<tex> B_{x_1,...,x_d} \subset \bigcup \limits _{k = 1}^n A_k \iff B_{x_1,...,x_d} \subset A_k \iff</tex>
Выберем <tex>\epsilon : \epsilon_s, \epsilon_p, \epsilon_v \leq \frac{\epsilon^2}{47n}</tex>.
Если все используемые тела являются гиперкубамигиперпараллелепипедами, то время работы каждого из оракулов составляет в точности <tex>O(d)</tex>, таким образом алгоритм позволяет построить <tex>\epsilon</tex>-аппроксимацию гиперобъема с вероятностью <tex>\geq 3/4</tex> за время <tex>O(\frac{nd}{\epsilon^2})</tex>.
==Источники==
<references />
