Изменения

Утверждается, что точное вычисление значения гиперобъема множества из <tex>n</tex> точек <tex>d</tex>-мерного пространства является [http://en.wikipedia.org/wiki/Sharp-P #P-трудной задачей], однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за*полином от количества параметров,*полином от количества решений,*полином от качества аппроксимации. == Постановка #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>x }} {{Теорема|statement= Задача вычисления гиперобъема принадлежит классу #P-трудных задач|proof= (x_1Суть доказательства состоит в сведении задачи #MON-CNF к задаче вычисления значения гиперобъема. Так как доказано<ref> Roth D. On the hardness of approximate reasoning, Artif. Intell., 82: 273–302, x_21996, http://cogcomp.cs.illinois.edu/papers/hardJ.pdf</ref>, x_d; что #MON-CNF является #P-трудной, то это докажет теорему. Количество удовлетворяющих подстановок функции<tex>f = \bigwedge \limits _{k=1}^n \bigvee_{i \in C_k} x_i</tex>меньше <tex>2^d</tex> на количество удовлетворяющих подстановок ее отрицания<tex> \overline{f} = \bigvee \limits _{k=1}^n \bigwedge_{i \in C_k} \neg x_i</tex>. Для упрощения вычислений далее будем работать с <tex>\overline{f}</tex>. Для каждого конъюнкта <tex>\bigwedge_{i \in C_k} \neg x_i </tex> построим соответствующий ему гиперпараллелепипед<tex>A_k = [0,a^k_1]\times...\ge times[0) ,a^k_d]</tex> где  <tex>a^k_i = \begin{cases} 1 & \text{if } i \in RC_k \\ 2 & \text{otherwise}\end{cases}</tex>. Рассмотрим теперь <tex>A = \bigcup \limits _{k=1}^dn 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>xA_i</tex> доминирует точку <tex>y</tex> (<tex>x \succ y</tex>), если каждый из этих гиперкубов лежит в хотя бы одном из <tex>\forall i : x_i \ge y_i, \exists j : x_j > y_jA_i</tex>.

<tex>X = (x^1, x^2B_{x_1, ..., x^n) x_d} \subset R\bigcup \limits _{k = 1}^d</tex> - множество из <tex>n</tex> точек в <tex>d</tex>-мерном пространстве такихA_k \iff B_{x_1,..., что <tex>x_d} \nexists i subset A_k \neq j : x_i \succ x_jiff</tex> - никакая точка не доминируется другой точкой из этого множества.

А значит из определения <tex>S(X) = \mu (\bigcup \limits_{x \in X} \{y | y \succ x\}) A_i</tex> - гиперобъем множества <tex>X</tex>.

В частности, если <tex>X = \{xiff\}</tex>, то <tex>S(X) = exists a^k_i \prod geq x_i + 1 : i \limits_{i=1}^{in d} x_i \iff</tex>.

Утверждается, что точное вычисление значения гиперобъема <tex>S\iff \forall i : x_i = 1 \to a^k_i = 2 \iff \forall i : x_i = 1 \to i \notin C_k \iff (Xx_1,...,x_d)</tex> множества из удовлетворяет <tex>n\bigwedge_{i \in C_k} \neg x_i</tex> точек для некоторого <tex>dk \iff (x_1,...,x_d)</tex>-мерного пространства является [http:удовлетворяет <tex>\overline{f}<//en.wikipedia.org/wiki/Sharp-P #P-трудной задачей], однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за*полином от количество параметров,*полином от количества решений,*полином от качества аппроксимации.tex>

Заметим, что так как <tex>\mu (B_{x_1,...,x_d}) =1 \to \mu (\bigcup \limits _{k= #P-трудность задачи вычисления гиперобъема 1}^n A_k ) ==Доказательство будет состоять в сведении задачи #MON-CNF |\{(Satisfability problem for monotone boolean formulasx_1,...,x_d)\in \{0,1\}^d| (x_1,...,x_d)</tex> удовлетворяет <tex>\overline{f} \}|</tex>

{{Определение|definition=Таким образом произвели сведение, в значит задача вычисления гиперобъема принадлежит классу #MON-CNF -- задача вычисления количества удовлетворяющих подстановок для монотонной булевой формулы, записанной в КНФ <tex>f = \bigwedge \limits _{k=1}^n \bigvee_{i \in C_k} x_i</tex>где клозы <tex> C_k \subseteq {1,...,d}</tex>P

Задача #MON==Эффективная аппроксимация нахождения значения гиперобъема==Приведем псевдокод алгоритма для аппроксимации гиперобъема объединения тел. В алгоритме, приведенном в <ref>Bringmann K., Friedrich T. Approximating the volume of unions and intersections of high-CNF является #Pdimensional 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> соответственно. Оракул*<tt>PointQuery(x,B)</tt> возвращает true, если точка <tex>x</tex> лежит внутри <tex> B</tex>.*<tt>VolumeQuery(B)</tt> возвращает объем заданного тела <tex>B</tex>.Сведем ее к задаче вычисления гиперобъема*<tt>SampleQuery(B)</tt> для заданного тела <tex>B</tex> возвращает произвольную его точку <tex>x \in B</tex>.  Для данного алгоритма допускаются следующие ослабления этих оракулов:*<tt>PointQuery(x,B)</tt> возвращает true для MONвсех точек из некоторого тела <tex> B' : \mu ((B' \backslash B) \cup (B \backslash B'))\leq \epsilon_p \mu(B)</tex>*<tt>VolumeQuery(B)</tt> возвращает значение <tex>V' : (1-\epsilon_v)\mu(B) \leq V' \leq (1+\epsilon_v)\mu(B)</tex>*<tt>SampleQuery(B)</tt> возвращает произвольную точку из тела <tex>B' : |f(x) - 1/\mu(B')| < \epsilon_s </tex> M := 0; C := 0; <tex> \overline \epsilon := \frac{\epsilon - \epsilon_v}{1+ \epsilon_v} </tex> <tex> \overline C := \frac{(1+\epsilon_s)(1+\epsilon_v)(1+\epsilon_p)}{(1-\epsilon_v)(1-CNF формулы\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 <tex> V' := \sum\limits_{i = 1}^n V'_i</tex> while <tex>C \leq T</tex> do choose <tex>i \in [n] </tex> with probability <tex>\frac{V'_i}{V'}</tex> x := SampleQuery(<tex>B_i</tex>) repeat if (C > T) then return <tex>\frac {TV'}{nM} </tex> choose random <tex>j \in [n]</tex> uniformly C := C + 1 until PointQuery (x, <tex>B_j</tex>) M := M + 1 od return <tex>\frac{TV'}{nM}</tex> Время работы алгоритма составляет  <tex>O(n V(d)+M S(d)+ TP(d)) = O(n V(d) + T(S(d)+P(d)) )</tex>,

где <tex>f = V(d)</tex>, <tex>S(d)</tex> и <tex>P(d)</tex> это оценка времени работы оракулов <tt>VolumeQuery</tt>, <tt>SampleQuery</tt> и <tt>PointQuery</tt>, соответственно. Выберем <tex>\epsilon : \epsilon_s, \bigwedge epsilon_p, \limits _epsilon_v \leq \frac{k=1\epsilon^2}^n \bigvee_{i \in C_k47n} x_i</tex>.

<tex> \overline{f} = \bigvee \limits _{k=1}^n \bigwedge_{i \in C_k} \not x_iИсточники==<references /tex>