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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Утверждается, что точное вычисление значения гиперобъема [math]S(X)[/math] множества из [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 к задаче вычисления значения гиперобъема. Так как доказано [1] , что #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]

Примечания

  1. Karl Bringmann, Tobias Friedrich, 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