42
правки
Изменения
Нет описания правки
|proof= Суть доказательства состоит в сведении задачи #MON-CNF к задаче вычисления значения гиперобъема. Так как доказано
<ref>
Roth D., On the hardness of approximate reasoning, Artif. Intell., 82: 273–302, 1996, http://cogcomp.cs.illinois.edu/papers/hardJ.pdf
</ref>
, что #MON-CNF является #P-трудной, то это докажет теорему.
<tex>\iff \forall i : x_i = 1 \to a^k_i = 2 \iff \forall i : x_i = 1 \to i \notin C_k \iff (x_1,...,x_d) </tex> удовлетворяет <tex>\bigwedge_{i \in C_k} \neg x_i</tex> для некоторого <tex>k \iff (x_1,...,x_d)</tex> удовлетворяет <tex>\overline{f}</tex>
Заметим, что так как <tex>\mu (B_{x_1,...,x_d}) = 1 \to \mu (\bigcup \limits _{k=1}^nA_k ) A_k = |\{(x_1,...,x_d) \in \{0,1\}^d| (x_1,...,x_d)</tex> удовлетворяет <tex>\overline{f} \}|</tex>
Таким образом произвели сведение, в значит задача вычисления гиперобъема принадлежит классу #P
Приведем псевдокод алгоритма для аппроксимации гиперобъема объединения тел. В алгоритме, приведенном в
<ref>
Bringmann K., Friedrich T., Approximating the volume of unions and intersections of high-dimensional geometric objects, ISAAC'2008, http://www.mpi-inf.mpg.de/~kbringma/paper/2008ISAAC_Volume.pdf
</ref>
используются три оракула: <tt>PointQuery</tt>, <tt>VolumeQuery</tt> и <tt>SampleQuery</tt>, каждый из которых ошибается с вероятностью <tex>\epsilon_p, \epsilon_v</tex> и <tex>\epsilon_s</tex> соответственно.
<tex> \overline C := \frac{(1+\epsilon_s)(1+\epsilon_v)(1+\epsilon_p)}{(1-\epsilon_v)(1-\epsilon_p)}</tex>
<tex> T := \frac{24 ln (2) (1 + \overline \epsilon) n}{\overline \epsilon^2 - 8 (\overline C - 1) n}</tex>
for all <tex>B_i \in S</tex>do
compute <tex>V'_i</tex> := VolumeQuery(<tex>B_i</tex>)
od
