Сложность задачи вычисления Least Hypervolume Contributor и задачи его аппроксимации — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 16 промежуточных версий 5 участников) | |||
Строка 1: | Строка 1: | ||
− | + | Гиперобъем является индикатором Парето-фронта, набирающим в последнее время популярность<ref>[http://www.mpi-inf.mpg.de/~tfried/paper/2009GECCO.pdf Friedrich T., Horoba C., Neumann F. — Multiplicative Approximations and the Hypervolume Indicator (2009)]</ref><ref>[http://www.mpi-inf.mpg.de/~tfried/paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. — The Maximum Hypervolume Set Yields Near-optimal Approximation (2010)]</ref>. Важной составляющей многих оптимизирующих алгоритмов, использующих индикатор гиперобъема, является вычисление вклада одного элемента Парето-фронта. К сожалению, даже вычисление минимального вклада (Minimal Contribution, MINCON) и нахождение соответствующего ему элемента (Least Contributor, LC) являются трудными задачами. Более того, даже аппроксимации этих задач являются NP-трудными<ref>[http://www.mpi-inf.mpg.de/~tfried/paper/2009EMO.pdf Bringmann K., Friedrich T. Approximating the least hypervolume contributor: NP-hard in general, but fast in practice (2009)]</ref>. | |
== Используемые обозначения == | == Используемые обозначения == | ||
− | <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>\mathrm{CON}(M, x) := \mathrm{HYP}(M) - \mathrm{HYP}(M \setminus x)</tex> – вклад элемента <tex>x \in M</tex> в гиперобъем. |
− | <tex>\mathrm{MINCON}(M) := \min \limits_{x \in M} \mathrm{CON}(M, x)</tex> | + | <tex>\mathrm{MINCON}(M) := \min \limits_{x \in M} \mathrm{CON}(M, x)</tex> – минимальный вклад в гиперобъем множества. Задача MINCON – задача нахождения <tex>\mathrm{MINCON}(M)</tex>. |
− | <tex>\mathrm{LC}(M) := \mathrm{argmin}_{x \in M} \mathrm{CON}(M, x)</tex> | + | <tex>\mathrm{LC}(M) := \mathrm{argmin}_{x \in M} \mathrm{CON}(M, x)</tex> – least contributor, минимальный вкладчик, элемент, имеющей минимальный вклад в гиперобъем. Задача LC – задача нахождения <tex>\mathrm{LC}(M)</tex>. |
− | <tex>\varepsilon\text{-}\mathrm{LC}(M)</tex> | + | <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>. | + | <tex>\mathrm{CON}(M, \varepsilon\text{-}\mathrm{LC}(M)) \le (1 + \varepsilon)\mathrm{MINCON}(M)</tex>. Задача <tex>\varepsilon</tex>-LC – задача нахождения <tex>\varepsilon\text{-}\mathrm{LC}(M)</tex>. |
+ | |||
+ | Все числа, за исключением <tex>\varepsilon</tex>, будем считать целыми. | ||
== Сложность задачи MINCON == | == Сложность задачи MINCON == | ||
Строка 19: | Строка 21: | ||
|statement= | |statement= | ||
− | Задача MINCON является #P- | + | Задача MINCON является #P-трудной, а задача аппроксимации MINCON с точностью до <tex>2^{d^{1 - \varepsilon}}</tex> является NP-трудной для любого <tex>\varepsilon > 0</tex>. |
|proof= | |proof= | ||
Для доказательства теоремы сведем задачу #MON-CNF к задаче MINCON. | Для доказательства теоремы сведем задачу #MON-CNF к задаче MINCON. | ||
− | Про задачу #MON-CNF известно, что она является #P- | + | Про задачу #MON-CNF известно, что она является #P-трудной, а ее аппроксимация является NP-трудной. |
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Задача #MON-CNF | + | Задача #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> C_k \subseteq {\{1,...,d\}}</tex>. | ||
}} | }} | ||
− | За <tex>\Box(a_1, \ldots, a_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>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>a_i^k = | ||
Строка 46: | Строка 47: | ||
</tex> | </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>n + 1</tex> элемента <tex>\{A_1, \ldots, A_n, B\}</tex>. Не умаляя общности, будем считать, что ни один клоз не доминируется |
другим, то есть <tex>C_i \nsubseteq C_j</tex> для любых <tex>i \neq j</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>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>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</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 | + | Представим <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>\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>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>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>(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>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>\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 является | + | Из-за сведения получаем, что задача MINCON является #P-трудной, а ее аппроксимация является NP-трудной, даже когда минимальный вкладчик уже известен. |
}} | }} | ||
Строка 69: | Строка 70: | ||
|statement= | |statement= | ||
− | Задача <tex>\varepsilon</tex>-LC является NP- | + | Задача <tex>\varepsilon</tex>-LC является NP-трудной. |
|proof= | |proof= | ||
− | Для | + | Для доказательства этой теоремы сведем задачу MINCON к задаче <tex>\varepsilon</tex>-LC. Не умаляя общности, будем считать, что <tex>d \ge 2</tex>, так как для |
<tex>d = 1</tex> задача становится тривиальной. Также будем считать, что <tex>\mathrm{MINCON}(M) > 0</tex>. | <tex>d = 1</tex> задача становится тривиальной. Также будем считать, что <tex>\mathrm{MINCON}(M) > 0</tex>. | ||
− | Пусть <tex>V</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>A = \left\{\Box\left(a_1 + 2V, a_2, \ldots, a_d\right) | \left(a_1, \ldots, a_d\right) \in M\right\}</tex>, | ||
Строка 88: | Строка 89: | ||
<tex>M_{\lambda} = A \cup \{B\} \cup \{ C_{\lambda} \}</tex>. | <tex>M_{\lambda} = A \cup \{B\} \cup \{ C_{\lambda} \}</tex>. | ||
− | Исходные элементы были сдвинуты вдоль первой оси, поэтому вклад этих элементов не | + | Исходные элементы были сдвинуты вдоль первой оси, поэтому вклад этих элементов не изменился, так как добавленная часть покрывается новым элементом <tex>B</tex>. |
Также отметим, что вклад каждого из элементов множества <tex>A</tex> не превышает <tex>V</tex>. | Также отметим, что вклад каждого из элементов множества <tex>A</tex> не превышает <tex>V</tex>. | ||
Элемент <tex>B</tex> единственный, кто покрывает область <tex>[V, 2V] \times \ldots \times [V, 2V]</tex>, объем которой превышает <tex>V</tex>. Единственным кандидатом на | Элемент <tex>B</tex> единственный, кто покрывает область <tex>[V, 2V] \times \ldots \times [V, 2V]</tex>, объем которой превышает <tex>V</tex>. Единственным кандидатом на | ||
− | должность минимального вкладчика, не | + | должность минимального вкладчика, не присутствовавшего в начальном множестве <tex>M</tex>, является элемент <tex>C_{\lambda}</tex>. Его вклад в точности соответствует области |
<tex>[0, 1] \times \ldots \times [0, 1] \times [2V, 2V + \lambda]</tex>, объем которой равен <tex>\lambda</tex>. | <tex>[0, 1] \times \ldots \times [0, 1] \times [2V, 2V + \lambda]</tex>, объем которой равен <tex>\lambda</tex>. | ||
− | Таким образом, элемент <tex>C_{\lambda}</tex> является минимальным вкладчиком только | + | Таким образом, элемент <tex>C_{\lambda}</tex> является минимальным вкладчиком только при условии <tex>\lambda \le \mathrm{MINCON}(M)</tex>. |
Так как умея решать задачу LC, мы можем проверять, является ли <tex>C_{\lambda}</tex> минимальным вкладчиком, можно | Так как умея решать задачу LC, мы можем проверять, является ли <tex>C_{\lambda}</tex> минимальным вкладчиком, можно | ||
− | устроить двоичный поиск по | + | устроить двоичный поиск по величине <tex>\lambda</tex>, чтобы найти <tex>\mathrm{MINCON}(M)</tex>, что |
− | потребует <tex>\ | + | потребует <tex>O(\log(V))</tex> шагов. Однако в случае <tex>\varepsilon</tex>-LC запросов |
− | обычный двоичный | + | обычный двоичный поиcк осуществить не удается. Несмотря на появившуюся неточность, продолжим выполнять |
все шаги двоичного поиска как обычно. | все шаги двоичного поиска как обычно. | ||
− | Использование <tex>\varepsilon</tex>-LC может привести двоичный поиск | + | Использование <tex>\varepsilon</tex>-LC может привести двоичный поиск не туда. |
− | <tex>\mathrm{CON}(M, \varepsilon\text{-LC}(M)) \le (1 + \varepsilon) \mathrm{MINCON}(M)</tex>, то неправильный ответ | + | Будем искать только старший бит ответа, то есть положим <tex>\lambda = 2^{\kappa}</tex>, где <tex>\kappa</tex> – целое число. |
+ | Так как мы имеем <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>(1 + \varepsilon)^{-1}\mathrm{MINCON}(M) \le 2^{\kappa} \le (1 + \varepsilon)\mathrm{MINCON}(M)</tex>. | ||
Вне этого интервала результат запроса всегда верен. | Вне этого интервала результат запроса всегда верен. | ||
− | Используя такой двоичный поиск мы получим число <tex>\kappa</tex>, которое или попадает в указанный интервал, и тогда задача решена, или является | + | Используя такой двоичный поиск, мы получим число <tex>\kappa</tex>, которое или попадает в указанный интервал, и тогда задача решена, или является |
− | максимальным целым числом меньшим <tex>(1 + \varepsilon)^{-1}\mathrm{MINCON}(M)</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> | + | Таким образом, <tex>\lambda = 2^{\kappa} \ge \mathrm{MINCON}(M) / (2(1 + \varepsilon))</tex>, то есть была получена <tex>2(1 + \varepsilon)</tex> аппроксимация задачи MINCON. |
− | аппроксимация задачи MINCON | + | |
+ | Ранее было показано, что аппроксимация задачи MINCON является NP-трудной, таким образом, NP-трудность задачи <tex>\varepsilon</tex>-LC доказана. | ||
}} | }} | ||
− | + | = Источники = | |
− | + | <references /> |
Текущая версия на 19:19, 4 сентября 2022
Гиперобъем является индикатором Парето-фронта, набирающим в последнее время популярность[1][2]. Важной составляющей многих оптимизирующих алгоритмов, использующих индикатор гиперобъема, является вычисление вклада одного элемента Парето-фронта. К сожалению, даже вычисление минимального вклада (Minimal Contribution, MINCON) и нахождение соответствующего ему элемента (Least Contributor, LC) являются трудными задачами. Более того, даже аппроксимации этих задач являются NP-трудными[3].
Содержание
Используемые обозначения
– гиперобъем множества .
– вклад элемента в гиперобъем.
– минимальный вклад в гиперобъем множества. Задача MINCON – задача нахождения .
– least contributor, минимальный вкладчик, элемент, имеющей минимальный вклад в гиперобъем. Задача LC – задача нахождения .
– элемент, имеющий вклад, отличающийся от минимального не более, чем в раз, то есть . Задача -LC – задача нахождения .
Все числа, за исключением
, будем считать целыми.Сложность задачи MINCON
Теорема: | ||
Задача MINCON является #P-трудной, а задача аппроксимации MINCON с точностью до является NP-трудной для любого . | ||
Доказательство: | ||
Для доказательства теоремы сведем задачу #MON-CNF к задаче MINCON. Про задачу #MON-CNF известно, что она является #P-трудной, а ее аппроксимация является NP-трудной.
Также добавим параллелепипед . Таким образом, множество будет состоять из элемента . Не умаляя общности, будем считать, что ни один клоз не доминируется другим, то есть для любых . Для каждого существуют такие , что область уникально покрывается только элементом , что означается, что для любого . Так как объем составляет лишь , то именно будет являться минимальным вкладчиком.Представим Из-за сведения получаем, что задача MINCON является #P-трудной, а ее аппроксимация является NP-трудной, даже когда минимальный вкладчик уже известен. в виде набора кубиков , где . Чтобы входил в , необходимо, чтобы не входил в . входит в , если для всех выполнено , то есть для всех , и . Получаем, что такой набор удовлетворяет для какого-то , то есть удовлетворяет . Таким образом, тогда и только тогда, когда удовлетворяет , то есть . | ||
Сложность задачи -LC
Теорема: |
Задача -LC является NP-трудной. |
Доказательство: |
Для доказательства этой теоремы сведем задачу MINCON к задаче -LC. Не умаляя общности, будем считать, что , так как для задача становится тривиальной. Также будем считать, что .Пусть – размер обрамляющего прямоугольного параллелепипеда множества . Очевидно, что .Определим новое множество элементов: , , , . Исходные элементы были сдвинуты вдоль первой оси, поэтому вклад этих элементов не изменился, так как добавленная часть покрывается новым элементом . Также отметим, что вклад каждого из элементов множества не превышает .Элемент единственный, кто покрывает область , объем которой превышает . Единственным кандидатом на должность минимального вкладчика, не присутствовавшего в начальном множестве , является элемент . Его вклад в точности соответствует области , объем которой равен . Таким образом, элемент является минимальным вкладчиком только при условии .Так как умея решать задачу LC, мы можем проверять, является ли минимальным вкладчиком, можно устроить двоичный поиск по величине , чтобы найти , что потребует шагов. Однако в случае -LC запросов обычный двоичный поиcк осуществить не удается. Несмотря на появившуюся неточность, продолжим выполнять все шаги двоичного поиска как обычно.Использование Ранее было показано, что аппроксимация задачи MINCON является NP-трудной, таким образом, NP-трудность задачи -LC может привести двоичный поиск не туда. Будем искать только старший бит ответа, то есть положим , где – целое число. Так как мы имеем , то неправильный ответ на запрос может выдаваться только при . Вне этого интервала результат запроса всегда верен. Используя такой двоичный поиск, мы получим число , которое или попадает в указанный интервал, и тогда задача решена, или является максимальным целым числом, меньшим . Таким образом, , то есть была получена аппроксимация задачи MINCON. -LC доказана. |
Источники
- ↑ Friedrich T., Horoba C., Neumann F. — Multiplicative Approximations and the Hypervolume Indicator (2009)
- ↑ Friedrich T., Bringmann K. — The Maximum Hypervolume Set Yields Near-optimal Approximation (2010)
- ↑ Bringmann K., Friedrich T. Approximating the least hypervolume contributor: NP-hard in general, but fast in practice (2009)