Изменения

[[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема| Определение Гиперобъемагиперобъема]]

Утверждается, что точное вычисление значения гиперобъема <tex>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространства является [http://en.wikipedia.org/wiki/Sharp-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>,

|statement= Задача вычисления гиперобъема принадлежит классу #P -трудных задач|proof= Суть доказательства состоит в сведении задачи #MON-CNF к задаче вычисления значения гиперобъема. Так как доказано<ref> Roth D. On the hardness of approximate reasoning, Artif. Intell., 82: 273–302, 1996, http://cogcomp.cs.illinois.edu/papers/hardJ.pdf</ref>, что #MON-CNF является #P-трудной, то это докажет теорему.Задача MON-CNF состоит в нахождении количества Количество удовлетворяющих подстановок дляфункции

 Количество ее удовлетворяющих подстановок равно меньше <tex>2^d</tex> минус на количество удовлетворяющих подстановок ее отрицания

поэтому далее будем работать с <tex>\overline{f}</tex>.Для каждого клоза конъюнкта <tex>\bigwedge_{i \in C_k} \neg x_i</tex> построим гиперкуб соответствующий ему гиперпараллелепипед<tex>A_k = [0,a^k_1]\times...\times[0,a^k_d]</tex>

</tex> например, гиперкубу .

Рассмотрим теперь <tex>C_1 A = \bigcup \limits _{k=1}^n A_k</tex>. Заметим, что так как все вершины гиперпараллелепипедов <tex>A_i</tex> лежат в точках с целочисленными координатами 0,1 или 2, то и <tex>A</tex> можно разбить на гиперкубы вида <tex>B_{xx_1,...,x_d} = [x_1,x_1 + 1]\}times ... \times [x_d, x_d + 1]</tex> будет соответствовать клоз , где <tex>x_i \neg x_1in \{0,1\}, i \in [d]</tex>(то есть на гиперкубы со сторонами 1 с координатами ближайшей к началу координат вершины 0 или 1).

а Более того, из-за целочисленности вершин <tex>C_2 = \{1,2\}A_i</tex> клоз , каждый из этих гиперкубов лежит в хотя бы одном из <tex>\neg x_1 \wedge \neg x_2A_i</tex>.

Заметим, что объединение гиперкубов <tex>A_k</tex> может быть записано как объединение гиперкубов вида <tex>B_{x_1,...,x_d} \subset \bigcup \limits _{k = [1}^n A_k \iff B_{x_1,x_1 + 1]\times ... \times [x_d, x_d + 1]</tex>, где <tex>x_i } \in \{0,1subset A_k \}, i \in [d]iff</tex>.

<tex> 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</tex>

Заметим, что так как <tex>\mu (B_{x_1,...,x_d}) = 1 \to \mu (\bigcup \limits _{k=1}^nA_k ) A_k = |\{(x_1,...,x_d) \in \{0,1\}^d| (x_1,...,x_d)</tex> удовлетворяет <tex>\overline{f}\}|</tex>

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