Изменения
Нет описания правки
<tex>\mathrm{LC}(M) := \mathrm{argmin}_{x \in M} \mathrm{CON}(M, x)</tex> – least contributor, минимальный вкладчик, элемент, имеющей минимальный вклад в гиперобъем.
<tex>\varepsilon\text{-}\mathrm{LC}(M)</tex> – элемент, имеющий вклад, отличающийся от минимального не более , чем в <tex>1 + \varepsilon</tex> раз, то есть
<tex>\mathrm{CON}(M, \varepsilon\text{-}\mathrm{LC}(M)) \le (1 + \varepsilon)\mathrm{MINCON}(M)</tex>.
|statement=
Задача MINCON является #P-трудной, а задача аппроксимации MINCON с точностью до <tex>2^{d^{1 - \varepsilon}}</tex> является NP-трудной для любого <tex>\varepsilon > 0</tex>.
|proof=
}}
За <tex>\Box(a_1, \ldots, a_d)</tex> будем обозначать прямоугольный гиперпараллелипипед гиперпараллелепипед <tex>[0, a_1] \times \ldots \times [0, a_d]</tex>.
Пусть <tex>f = \bigwedge \limits_{k=1}^n \bigvee \limits_{i \in C_k} x_i</tex> – монотонная булева формула в КНФ, <tex> C_k \subseteq {\{1,...,d\}}</tex>.
Построим параллелипипеды параллелепипеды <tex>A_k = \Box(a_1^k, \ldots, a_d^k, 2^d + 2) \subseteq \mathbb{R}^{d+1}</tex> для каждого клоза формулы, при этом
<tex>a_i^k =
</tex>
Также добавим параллелипипед параллелепипед <tex>B = \Box(2, \ldots, 2, 1) \subseteq \mathbb{R}^{d+1}</tex>. Таким образом , множество <tex>M</tex> будет
состоять из <tex>n + 1</tex> элемента <tex>\{A_1, \ldots, A_n, B\}</tex>. Не умаляя общности, будем считать, что ни один клоз не доминируется
другим, то есть <tex>C_i \nsubseteq C_j</tex> для любых <tex>i \neq j</tex>.
и <tex>i \notin C_k</tex>. Получаем, что такой набор <tex>(x_1, \ldots, x_d)</tex> удовлетворяет <tex>\bigwedge \limits_{i \in C_k} \lnot x_i</tex> для какого-то <tex>k</tex>, то
есть <tex>(x_1, \ldots, x_d)</tex> удовлетворяет <tex>\overline{f} = \bigvee \limits_{k=1}^n \bigwedge \limits_{i \in C_k} \lnot x_i</tex>.
Таким образом , <tex>B_x \subseteq \mathrm{CON}(M, B)</tex> тогда и только тогда, когда <tex>(x_1, \ldots, x_d)</tex> удовлетворяет <tex>f</tex>, то есть
<tex>\mathrm{MINCON}(M) = \mathrm{CON}(M, B) = \left\vert\left\{ \left(x_1, \ldots, x_d \right) \in \left\{0, 1\right\}^d | \left(x_1, \ldots, x_d \right) \text{ satisfies } f \right\}\right\vert</tex>.
<tex>d = 1</tex> задача становится тривиальной. Также будем считать, что <tex>\mathrm{MINCON}(M) > 0</tex>.
Пусть <tex>V</tex> – размер обрамляющего прямоугольного параллелипипеда параллелепипеда множества <tex>M</tex>. Очевидно, что <tex>V \le 2^{\text{input size}}</tex>.
Определим новое множество элементов:
Используя такой двоичный поиск, мы получим число <tex>\kappa</tex>, которое или попадает в указанный интервал, и тогда задача решена, или является
максимальным целым числом меньшим <tex>\log_2 \left((1 + \varepsilon)^{-1}\mathrm{MINCON}(M)\right)</tex>.
Таким образом , <tex>\lambda = 2^{\kappa} \ge \mathrm{MINCON}(M) / (2(1 + \varepsilon))</tex>, то есть была получена <tex>2(1 + \varepsilon)</tex> аппроксимация задачи MINCON.
Ранее было показано, что аппроксимация задачи MINCON является NP-трудной, таким образом , NP-трудность задачи <tex>\varepsilon</tex>-LC доказана.
}}
== Источники ==
# Bringmann K., Friedrich T. Approximating the least hypervolume contributor: NP-hard in general, but fast in practice (2009)
