Оценка сложности вычисления гиперобъема

Определение гиперобъема

Утверждается, что точное вычисление значения гиперобъема множества из [math]n[/math] точек [math]d[/math]-мерного пространства является #P-трудной задачей, однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за

• полином от количества параметров,
• полином от количества решений,
• полином от качества аппроксимации.

#P-трудность задачи вычисления гиперобъема

Определение:

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

Теорема:

Задача вычисления гиперобъема принадлежит классу #P-трудных задач

Доказательство:

[math]\triangleright[/math]

Суть доказательства состоит в сведении задачи #MON-CNF к задаче вычисления значения гиперобъема. Так как доказано , что #MON-CNF является #P-трудной, то это докажет теорему. Количество удовлетворяющих подстановок функции [math]f = \bigwedge \limits _{k=1}^n \bigvee_{i \in C_k} x_i[/math] меньше [math]2^d[/math] на количество удовлетворяющих подстановок ее отрицания [math] \overline{f} = \bigvee \limits _{k=1}^n \bigwedge_{i \in C_k} \neg x_i[/math] . Для упрощения вычислений далее будем работать с [math]\overline{f}[/math]. Для каждого конъюнкта [math]\bigwedge_{i \in C_k} \neg x_i[/math] построим соответствующий ему гиперкуб [math]A_k = [0,a^k_1]\times...\times[0,a^k_d][/math] где [math] a^k_i = \begin{cases} 1 & \text{if } i \in C_k \\ 2 & \text{otherwise} \end{cases} [/math]. Рассмотрим теперь [math]A = \bigcup \limits _{k=1}^n A_k[/math]. Заметим, что так как все вершины гиперкубов [math]A_i[/math] лежат в точках с целочисленными координатами 0,1 или 2, то и [math]A[/math] можно разбить на гиперкубы вида [math]B_{x_1,...,x_d} = [x_1,x_1 + 1]\times ... \times [x_d, x_d + 1][/math], где [math]x_i \in \{0,1\}, i \in [d][/math] (то есть на гиперкубики со сторонами 1 с координатами ближайшей к началу координат вершины 0 или 1). Более того, из-за целочисленности вершин [math]A_i[/math], каждый из этих гиперкубиков лежит в хотя бы одном из [math]A_i[/math] [math] B_{x_1,...,x_d} \subset \bigcup \limits _{k = 1}^n A_k \iff B_{x_1,...,x_d} \subset A_k \iff[/math] А значит из определения [math]A_i[/math] [math] \iff\exists a^k_i \geq x_i + 1 : i \in d \iff[/math] [math]\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) [/math] удовлетворяет [math]\bigwedge_{i \in C_k} \neg x_i[/math] для некоторого [math]k \iff (x_1,...,x_d)[/math] удовлетворяет [math]\overline{f}[/math] Заметим, что так как [math]\mu (B_{x_1,...,x_d}) = 1 \to \mu (\bigcup \limits _{k=1}^n) A_k = |\{(x_1,...,x_d) \in \{0,1\}^d| (x_1,...,x_d)[/math] удовлетворяет [math]\overline{f} \}|[/math] Таким образом произвели сведение, в значит задача вычисления гиперобъема принадлежит классу #P

[math]\triangleleft[/math]

Эффективная аппроксимация нахождения значения гиперобъема

Приведем псевдокод алгоритма для аппроксимации гиперобъема объединения тел. В алгоритме, приведенном в используются три оракула: PointQuery, VolumeQuery и SampleQuery, каждый из которых ошибается с вероятностью [math]\epsilon_p, \epsilon_v[/math] и [math]\epsilon_s[/math] соответственно.

Оракул

• PointQuery(x,B) возвращает true, если точка [math]x[/math] лежит внутри [math] B[/math].
• VolumeQuery(B) возвращает объем заданного тела [math]B[/math].
• SampleQuery(B) для заданного тела [math]B[/math] возвращает произвольную его точку [math]x \in B[/math].

Для данного алгоритма допускаются следующие ослабления этих оракулов:

• PointQuery (x,B) возвращает true для всех точек из некоторого тела [math] B' : \mu ((B' \backslash B) \cup (B \backslash B'))\leq \epsilon_p \mu(B)[/math]
• VolumeQuery(B) возвращает значение [math]V' : (1-\epsilon_v)\mu(B) \leq V' \leq (1+\epsilon_v)\mu(B)[/math]
• SampleQuery(B) возвращает произвольную точку из тела [math]B' : |f(x) - 1/\mu(B')| \lt \epsilon_s [/math]

M := 0; C := 0;
[math] \overline \epsilon := \frac{\epsilon - \epsilon_v}{1+ \epsilon_v} [/math]
[math] \overline C := \frac{(1+\epsilon_s)(1+\epsilon_v)(1+\epsilon_p)}{(1-\epsilon_v)(1-\epsilon_p)}[/math]
[math] T := \frac{24 ln (2) (1 + \overline \epsilon) n}{\overline \epsilon^2 - 8 (\overline C - 1) n}[/math]
for all [math]B_i \in S[/math]
 compute [math]V'_i[/math] := VolumeQuery([math]B_i[/math])
od
[math] V' := \sum\limits_{i = 1}^n V'_i[/math]
while [math]C \leq T[/math] do
 choose [math]i \in [n] [/math] with probability [math]\frac{V'_i}{V'}[/math]
 x := SampleQuery([math]B_i[/math])
 repeat 
  if (C > T) then return [math]\frac {TV'}{nM} [/math]
  choose random [math]j \in [n][/math] uniformly
  C := C + 1
 until PointQuery (x, [math]B_j[/math])
 M := M + 1
od
return [math]\frac{TV'}{nM}[/math]

Время работы алгоритма составляет

[math]O(n V(d)+M S(d)+ TP(d) = O(n V(d) + T(S(d)+P(d)))[/math],

где V(d), S(d) и P(d) это оценка времени работы оракулов VolumeQuery, SampleQuery и PointQuery, соответственно.

Выберем [math]\epsilon : \epsilon_s, \epsilon_p, \epsilon_v \leq \frac{\epsilon^2}{47n}[/math].

Если все используемые тела являются гиперкубами, то время работы каждого из оракулов составляет в точности [math]O(d)[/math], таким образом алгоритм позволяет построить [math]\epsilon[/math]-аппроксимацию гиперобъема с вероятностью [math]\geq 3/4[/math] за время [math]O(\frac{nd}{\epsilon^2})[/math]