Постановка задачи
[math]x = (x_1, x_2, ..., x_d; x_i \ge 0) \in R^d[/math] - точка в [math]d[/math]-мерном пространстве.
Точка [math]x[/math] доминирует точку [math]y[/math] ([math]x \succ y[/math]), если [math]\forall i : x_i \ge y_i, \exists j : x_j \gt y_j[/math].
[math]X = (x^1, x^2, ..., x^n) \subset R^d[/math] - множество из [math]n[/math] точек в [math]d[/math]-мерном пространстве таких, что [math]\nexists i \neq j : x_i \succ x_j[/math] - никакая точка не доминируется другой точкой из этого множества.
[math]S(X) = \mu (\bigcup \limits_{x \in X} \{y | y \succ x\}) [/math] - гиперобъем множества [math]X[/math].
В частности, если [math]X = \{x\}[/math], то [math]S(X) = \prod \limits_{i=1}^{d} x_i[/math].
Утверждается, что точное вычисление значения гиперобъема [math]S(X)[/math] множества из [math]n[/math] точек [math]d[/math]-мерного пространства является #P-трудной задачей, однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за
- полином от количество параметров,
- полином от количества решений,
- полином от качества аппроксимации.
#P-трудность задачи вычисления гиперобъема
Доказательство будет состоять в сведении задачи #MON-CNF (Satisfability problem for monotone boolean formulas).
| Определение: |
| задача #MON-CNF -- задача вычисления количества удовлетворяющих подстановок для монотонной булевой формулы, записанной в КНФ [math]f = \bigwedge \limits _{k=1}^n \bigvee_{i \in C_k} x_i[/math]
где клозы [math] C_k \subseteq {1,...,d}[/math] |
Задача #MON-CNF является #P-трудной
Сведем ее к задаче вычисления гиперобъема.
Задача MON-CNF состоит в нахождении количества удовлетворяющих подстановок для
[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]C_1 = \{x\}[/math] будет соответствовать клоз [math]\neg x_1[/math]
а [math]C_2 = \{1,2\}[/math] клоз [math]\neg x_1 \wedge \neg x_2[/math].
Заметим, что объединение гиперкубов [math]A_k[/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].
Более того,
[math] B_{x_1,...,x_d} \subset \bigcup \limits _{k = 1}^n A_k \iff B_{x_1,...,x_d} \subset A_k \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
