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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}} == Постановка задачи == <tex>x = (x_1, x_2, ..., x_d; x_i \ge 0) \in R^d</tex> - точка в <tex>d</tex>-мерн...»)
 
Строка 12: Строка 12:
 
В частности, если <tex>X = \{x\}</tex>, то <tex>S(X) = \prod \limits_{i=1}^{d} x_i</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>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространства является [http://en.wikipedia.org/wiki/Sharp-P #P-трудной задачей], а аппроксимация этого значения -- [[NP-полнота|NP-трудной]].

Версия 09:08, 18 июня 2012

Эта статья находится в разработке!

Постановка задачи

[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-трудной задачей, а аппроксимация этого значения -- NP-трудной.