42
правки
Изменения
Новая страница: «{{В разработке}} == Постановка задачи == <tex>x = (x_1, x_2, ..., x_d; x_i \ge 0) \in R^d</tex> - точка в <tex>d</tex>-мерн...»
{{В разработке}}
== Постановка задачи ==
<tex>x = (x_1, x_2, ..., x_d; x_i \ge 0) \in R^d</tex> - точка в <tex>d</tex>-мерном пространстве.
Точка <tex>x</tex> доминирует точку <tex>y</tex> (<tex>x \succ y</tex>), если <tex>\forall i : x_i \ge y_i, \exists j : x_j > y_j</tex>.
<tex>X = (x^1, x^2, ..., x^n) \subset R^d</tex> - множество из <tex>n</tex> точек в <tex>d</tex>-мерном пространстве таких, что <tex>\nexists i \neq j : x_i \succ x_j</tex> - никакая точка не доминируется другой точкой из этого множества.
<tex>S(X) = \mu (\bigcup \limits_{x \in X} \{y | y \succ x\}) </tex> - гиперобъем множества <tex>X</tex>.
В частности, если <tex>X = \{x\}</tex>, то <tex>S(X) = \prod \limits_{i=1}^{d} x_i</tex>.
Утверждается, что точное вычисление значения вклада одной точки в гиперобъем <tex>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространства является #P-трудной задачей, а аппроксимация этого значения -- NP-трудной.
== Постановка задачи ==
<tex>x = (x_1, x_2, ..., x_d; x_i \ge 0) \in R^d</tex> - точка в <tex>d</tex>-мерном пространстве.
Точка <tex>x</tex> доминирует точку <tex>y</tex> (<tex>x \succ y</tex>), если <tex>\forall i : x_i \ge y_i, \exists j : x_j > y_j</tex>.
<tex>X = (x^1, x^2, ..., x^n) \subset R^d</tex> - множество из <tex>n</tex> точек в <tex>d</tex>-мерном пространстве таких, что <tex>\nexists i \neq j : x_i \succ x_j</tex> - никакая точка не доминируется другой точкой из этого множества.
<tex>S(X) = \mu (\bigcup \limits_{x \in X} \{y | y \succ x\}) </tex> - гиперобъем множества <tex>X</tex>.
В частности, если <tex>X = \{x\}</tex>, то <tex>S(X) = \prod \limits_{i=1}^{d} x_i</tex>.
Утверждается, что точное вычисление значения вклада одной точки в гиперобъем <tex>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространства является #P-трудной задачей, а аппроксимация этого значения -- NP-трудной.
