Изменения
Новая страница: «{{В разработке}} == Используемые обозначения == <tex>\mathrm{HYP}\left(M\right)</tex> -- гиперобъем множеств...»
{{В разработке}}
== Используемые обозначения ==
<tex>\mathrm{HYP}\left(M\right)</tex> -- гиперобъем множества <tex>M</tex>.
<tex>\mathrm{CON}(M, x) := \mathrm{HYP}(M) - \mathrm{HYP}(M \ x)</tex> -- вклад элемента <tex>x \in M</tex> в гиперобъем.
<tex>\mathrm{MINCON}(M) := \min \limits_{x \in M} \mathrm{CON}(M, x)</tex> -- минимальный вклад в гиперобъем множества.
<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>.
== Сложность задачи MINCON ==
{{Теорема
|statement=
Задача MINCON является \#P-сложной, а задача аппроксимации с точностью до <tex>2^{d^{1 - \varepsilon}}</tex> является NP-сложной для любого <tex>\varepsilon > 0</tex>.
|proof=
Для доказательства теоремы сведем задачу \#MON-CNF к задаче MINCON.
Про задачу \#MON-CNF известно, что она является \#P-сложной, а ее аппроксимация является NP-сложной.
{{Определение
|definition=
Задача #MON-CNF -- задача нахождения числа удовлетворяющих подстановок для монотонной булевой формулы, записанной в КНФ <tex>f = \bigwedge \limits_{k=1}^n \bigvee \limits_{i \in C_k} x_i</tex>,
где клозы <tex> C_k \subseteq {\{1,...,d\}}</tex>.
}}
За <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 =
\begin{cases}
1,~\text{if}~i \in C_k \\
2,~\text{otherwise}
\end{cases}
</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>A_k</tex> существуют <tex>x_i = a_i^k - 1</tex> такие, что область <tex>[x_1, x_1 + 1] \times \ldots \times [x_d, x_d + 1] \times [1, 2^d + 2]</tex> уникально покрывается только
элементом <tex>A_k</tex>, что означается, что <tex>\mathrm{CON}(M, A_k) > 2^d</tex> для любого <tex>k</tex>. Так как объем <tex>B</tex> составляется лишь <tex>2^d</tex>, то
именно <tex>B</tex> будет являться минимальным вкладчиком.
Представим <tex>B</tex> в виде набора кубиков <tex>B_x = [x_1, x_1 + 1] \times \ldots \times [x_d, x_d + 1] \times [0, 1]</tex>, где <tex>x_i \in [0, 1]</tex>.
Чтобы <tex>B_x</tex> входил в <tex>\mathrm{CON}(M, B)</tex>, необходимо, чтобы <tex>B_x</tex> не входил в <tex>\bigcup \limits_{k = 1}^n A_k</tex>.
<tex>B_x</tex> входит в <tex>A_k</tex>, если для всех <tex>i \in \{1, \ldots, d\}</tex> выполнено <tex>x_i + 1 \le a_i^k</tex>, то есть <tex>a_i^k = 2</tex> для всех <tex>x_i = 1</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>.
Из-за сведения получаем, что задача MINCON является \#P-сложной, а ее аппроксимация является NP-сложной, даже когда минимальный вкладчик уже известен.
}}
== Сложность задачи <tex>\varepsilon</tex>-LC==
{{Теорема
|statement=
Задача <tex>\varepsilon</tex>-LC является NP-сложной.
|proof=
Для докозательства этой теоремы сведем задачу MINCON к задаче <tex>\varepsilon</tex>-LC. Не умаляя общности будем считать, что <tex>d \ge 2</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>A = \left\{\Box\left(a_1 + 2V, a_2, \ldots, a_d\right) | \left(a_1, \ldots, a_d\right) \in M\right\}</tex>,
<tex>B = \Box \left(2V, \ldots, 2V\right)</tex>,
<tex>C_{\lambda} = \Box \left(1, \ldots, 1, 2V + \lambda \right)</tex>,
<tex>M_{\lambda} = A \cup \{B\} \cup \{ C_{\lambda} \}</tex>.
Исходные элементы были сдвинуты вдоль первой оси, поэтому вклад этих элементов не изминился, так как добавленная часть также покрывается новым элементом <tex>B</tex>.
Также отметим, что вклад каждого из элементов множества <tex>A</tex> не превышает <tex>V</tex>.
Элемент <tex>B</tex> единственный, кто покрывает область <tex>[V, 2V] \times \ldots \times [V, 2V]</tex>, объем которой превышает <tex>V</tex>. Единственным кандидатом на
должность минимального вкладчика, не присутствовавшим в начальном множестве, является элемент <tex>C_{\lambda}</tex>. Его вклад в точности соответствуем области
<tex>[0, 1] \times \ldots \times [0, 1] \times [2V, 2V + \lambda]</tex>, объем которой равен <tex>\lambda</tex>.
Таким образом, элемент <tex>C_{\lambda}</tex> является минимальным вкладчиком только, если <tex>\lambda \le \mathrm{MINCON}(M)</tex>.
Так как умея решать задачу LC, мы можем проверять, является ли <tex>C_{\lambda}</tex> минимальным вкладчиком, можно
устроить двоичный поиск по велечине <tex>\lambda</tex>, чтобы найти <tex>\mathrm{MINCON}(M)</tex>, что
потребует <tex>\kappa := \log_2(\lambda)</tex> шагов. Однако в случае <tex>\varepsilon</tex>-LC запросов
обычный двоичный посик осуцществить не удается. Несмотря на появившуюся неточность, продолжим выполнять
все шаги двоичного поиска как обычно.
Использование <tex>\varepsilon</tex>-LC может привести двоичный поиск нетуда, но, так как мы имеем, что
<tex>\mathrm{CON}(M, \varepsilon\text{-LC}(M)) \le (1 + \varepsilon) \mathrm{MINCON}(M)</tex>, то неправильный ответ
на запрос может выдаваться только при <tex>(1 + \varepsilon)^{-1}\mathrm{MINCON}(M) \le 2^{\kappa} \le (1 + \varepsilon)\mathrm{MINCON}(M)</tex>.
Вне этого интервала результат запроса всегда верен.
Используя такой двоичный поиск мы получим число <tex>\kappa</tex>, которое или попадает в указанный интервал, и тогда задача решена, или является
максимальным целым числом меньшим <tex>(1 + \varepsilon)^{-1}\mathrm{MINCON}(M)</tex>.
Таким образом <tex>\lambda = 2^{\kappa} \ge \mathrm{MINCON}(M) / (2(1 + \varepsilon))</tex>, то есть была получена <tex>2(1 + \varepsilon)</tex>
аппроксимация задачи MINCON. NP-сложность задачи <tex>\varepsilon</tex>-LC доказана.
}}
== Источники ==
# [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/4/2009EMO.pdf Bringmann K., Friedrich T. Approximating the least hypervolume contributor: NP-hard in general, but fast in practice (2009)]
== Используемые обозначения ==
<tex>\mathrm{HYP}\left(M\right)</tex> -- гиперобъем множества <tex>M</tex>.
<tex>\mathrm{CON}(M, x) := \mathrm{HYP}(M) - \mathrm{HYP}(M \ x)</tex> -- вклад элемента <tex>x \in M</tex> в гиперобъем.
<tex>\mathrm{MINCON}(M) := \min \limits_{x \in M} \mathrm{CON}(M, x)</tex> -- минимальный вклад в гиперобъем множества.
<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>.
== Сложность задачи MINCON ==
{{Теорема
|statement=
Задача MINCON является \#P-сложной, а задача аппроксимации с точностью до <tex>2^{d^{1 - \varepsilon}}</tex> является NP-сложной для любого <tex>\varepsilon > 0</tex>.
|proof=
Для доказательства теоремы сведем задачу \#MON-CNF к задаче MINCON.
Про задачу \#MON-CNF известно, что она является \#P-сложной, а ее аппроксимация является NP-сложной.
{{Определение
|definition=
Задача #MON-CNF -- задача нахождения числа удовлетворяющих подстановок для монотонной булевой формулы, записанной в КНФ <tex>f = \bigwedge \limits_{k=1}^n \bigvee \limits_{i \in C_k} x_i</tex>,
где клозы <tex> C_k \subseteq {\{1,...,d\}}</tex>.
}}
За <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 =
\begin{cases}
1,~\text{if}~i \in C_k \\
2,~\text{otherwise}
\end{cases}
</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>A_k</tex> существуют <tex>x_i = a_i^k - 1</tex> такие, что область <tex>[x_1, x_1 + 1] \times \ldots \times [x_d, x_d + 1] \times [1, 2^d + 2]</tex> уникально покрывается только
элементом <tex>A_k</tex>, что означается, что <tex>\mathrm{CON}(M, A_k) > 2^d</tex> для любого <tex>k</tex>. Так как объем <tex>B</tex> составляется лишь <tex>2^d</tex>, то
именно <tex>B</tex> будет являться минимальным вкладчиком.
Представим <tex>B</tex> в виде набора кубиков <tex>B_x = [x_1, x_1 + 1] \times \ldots \times [x_d, x_d + 1] \times [0, 1]</tex>, где <tex>x_i \in [0, 1]</tex>.
Чтобы <tex>B_x</tex> входил в <tex>\mathrm{CON}(M, B)</tex>, необходимо, чтобы <tex>B_x</tex> не входил в <tex>\bigcup \limits_{k = 1}^n A_k</tex>.
<tex>B_x</tex> входит в <tex>A_k</tex>, если для всех <tex>i \in \{1, \ldots, d\}</tex> выполнено <tex>x_i + 1 \le a_i^k</tex>, то есть <tex>a_i^k = 2</tex> для всех <tex>x_i = 1</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>.
Из-за сведения получаем, что задача MINCON является \#P-сложной, а ее аппроксимация является NP-сложной, даже когда минимальный вкладчик уже известен.
}}
== Сложность задачи <tex>\varepsilon</tex>-LC==
{{Теорема
|statement=
Задача <tex>\varepsilon</tex>-LC является NP-сложной.
|proof=
Для докозательства этой теоремы сведем задачу MINCON к задаче <tex>\varepsilon</tex>-LC. Не умаляя общности будем считать, что <tex>d \ge 2</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>A = \left\{\Box\left(a_1 + 2V, a_2, \ldots, a_d\right) | \left(a_1, \ldots, a_d\right) \in M\right\}</tex>,
<tex>B = \Box \left(2V, \ldots, 2V\right)</tex>,
<tex>C_{\lambda} = \Box \left(1, \ldots, 1, 2V + \lambda \right)</tex>,
<tex>M_{\lambda} = A \cup \{B\} \cup \{ C_{\lambda} \}</tex>.
Исходные элементы были сдвинуты вдоль первой оси, поэтому вклад этих элементов не изминился, так как добавленная часть также покрывается новым элементом <tex>B</tex>.
Также отметим, что вклад каждого из элементов множества <tex>A</tex> не превышает <tex>V</tex>.
Элемент <tex>B</tex> единственный, кто покрывает область <tex>[V, 2V] \times \ldots \times [V, 2V]</tex>, объем которой превышает <tex>V</tex>. Единственным кандидатом на
должность минимального вкладчика, не присутствовавшим в начальном множестве, является элемент <tex>C_{\lambda}</tex>. Его вклад в точности соответствуем области
<tex>[0, 1] \times \ldots \times [0, 1] \times [2V, 2V + \lambda]</tex>, объем которой равен <tex>\lambda</tex>.
Таким образом, элемент <tex>C_{\lambda}</tex> является минимальным вкладчиком только, если <tex>\lambda \le \mathrm{MINCON}(M)</tex>.
Так как умея решать задачу LC, мы можем проверять, является ли <tex>C_{\lambda}</tex> минимальным вкладчиком, можно
устроить двоичный поиск по велечине <tex>\lambda</tex>, чтобы найти <tex>\mathrm{MINCON}(M)</tex>, что
потребует <tex>\kappa := \log_2(\lambda)</tex> шагов. Однако в случае <tex>\varepsilon</tex>-LC запросов
обычный двоичный посик осуцществить не удается. Несмотря на появившуюся неточность, продолжим выполнять
все шаги двоичного поиска как обычно.
Использование <tex>\varepsilon</tex>-LC может привести двоичный поиск нетуда, но, так как мы имеем, что
<tex>\mathrm{CON}(M, \varepsilon\text{-LC}(M)) \le (1 + \varepsilon) \mathrm{MINCON}(M)</tex>, то неправильный ответ
на запрос может выдаваться только при <tex>(1 + \varepsilon)^{-1}\mathrm{MINCON}(M) \le 2^{\kappa} \le (1 + \varepsilon)\mathrm{MINCON}(M)</tex>.
Вне этого интервала результат запроса всегда верен.
Используя такой двоичный поиск мы получим число <tex>\kappa</tex>, которое или попадает в указанный интервал, и тогда задача решена, или является
максимальным целым числом меньшим <tex>(1 + \varepsilon)^{-1}\mathrm{MINCON}(M)</tex>.
Таким образом <tex>\lambda = 2^{\kappa} \ge \mathrm{MINCON}(M) / (2(1 + \varepsilon))</tex>, то есть была получена <tex>2(1 + \varepsilon)</tex>
аппроксимация задачи MINCON. NP-сложность задачи <tex>\varepsilon</tex>-LC доказана.
}}
== Источники ==
# [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/4/2009EMO.pdf Bringmann K., Friedrich T. Approximating the least hypervolume contributor: NP-hard in general, but fast in practice (2009)]
