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

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

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

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

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

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

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

Теорема:

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

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

$\triangleright$

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

$\triangleleft$