Является ли правилом, что дискретные задачи являются NP-трудными, а непрерывные - нет?

В моем компьютерном образовании я все чаще замечаю, что большинство дискретных задач являются NP-полными (по крайней мере), тогда как оптимизация непрерывных задач почти всегда легко достижима, обычно с помощью градиентных методов. Есть ли исключения из этого?

Пример, который мне нравится, - это проблема, когда при различных решить, что: ∫ π - π cos ( a 1 z ) cos ( a 2 z ) … cos ( a n z $a_1, a_2, \ldots, a_n \in \mathbb{N}$

$\{a_1, \ldots, a_n\}$

$n$

Существует много непрерывных задач вида «проверить, может ли этот комбинаторный вклад быть реализован как геометрическая структура», которые являются законченными для экзистенциальной теории вещественных чисел , непрерывного аналога NP. В частности, это означает, что эти проблемы NP-трудны, а не полиномиально разрешимы. Примеры включают в себя тестирование того, является ли данный граф графом с единичным расстоянием, может ли данный граф быть нарисован в плоскости с краями отрезка прямой линии и не более чем заданным числом пересечений, или может ли данное псевдолиновое расположение растягиваться для формирования линии договоренность.

Существуют и другие непрерывные проблемы, которые еще сложнее: например, поиск кратчайшего пути среди многогранных препятствий в 3d является PSPACE-полным (Canny & Reif, FOCS'87).

Хотя это не совсем отвечает на ваш первоначальный вопрос, это (предположительный) пример своего рода философского контрапункта: проблема, когда презентация дискретна, но вся сложность проистекает из «непрерывного» аспекта проблемы.

$A=\{a_1, a_2, \ldots, a_m\}$$B=\{b_1, b_2, \ldots, b_n\}$$\sum_{i=1}^m \sqrt{a_i}\leq\sum_{j=1}^n\sqrt{b_j}$жесткий, широко распространено подозрение, что он может быть NP-сложным и может фактически быть за пределами NP (как отмечалось в комментариях, есть веские основания полагать, что он не является NP-завершенным); единственное известное на сегодняшний день ограничение - это несколько уровней выше полиномиальной иерархии. Очевидно, что представление этой проблемы настолько дискретно, насколько это возможно - набор целых чисел и вопрос «да / нет» о них - но проблема возникает потому, что, хотя вычисление квадратных корней с любой заданной точностью является простой задачей, их, возможно, потребуется вычислить с высокой (потенциально суперполиномиальной) точностью, чтобы решить неравенство тем или иным способом. Это «дискретная» проблема, которая возникает в удивительном количестве оптимизационных контекстов и помогает внести свой вклад в их собственную сложность.

Дискретные проблемы обычно бывают сложнее (например, LP против ILP), но проблема не в самой дискретности, а в том, как ограничения влияют на поиск в вашем домене. Например, вы можете подумать, что оптимизация многочлена - это то, что вы можете сделать эффективно, но решение выпуклости квартик (многочленов степени 4) является NP-трудным .

Это означает, что даже если у вас уже есть какой-то оптимум, просто доказать, что вы достигли оптимального уровня, уже сложно.

Хотя для некоторых популярных проблем это действительно так, я думаю, что оба предположения - в зависимости от того, что вы определяете как проблему оптимизации - не соответствуют действительности.

Сначала несколько определений: большинство проблем оптимизации не являются частью NP . Например, для задачи о ранце : нельзя использовать недетерминизм для создания наиболее ценного пакета, просто потому, что разные недетерминированные ветви не имеют общей памяти. NP также определяется как «проверяемый полиномами» (проверка сертификата) [1, p. 34]. В этом случае сертификат является, например, сумкой : цепочкой битов, где, если установлен i-й бит, это означает, что i-й элемент является частью пакета. Вы можете действительно проверить за полиномиальное время, является ли такой мешок более ценным, чем данный порог (это вариант решения), но вы не можете - насколько нам известно - основываясь на одной сумке (полиномиальном количестве сумок), решить, является ли эта сумка наиболее ценной из всех возможных сумок. Это жизненно важное различие между, например, NP и EXP : в EXP вы можете перечислять все возможные пакеты и вести учет того, какой пакет является лучшим.

Вариант решения проблем оптимизации в некоторых случаях является частью NP , необходимо провести четкое различие между максимизацией вкуса и принятием решения . В варианте решения вопрос: « Учитывая проблему оптимизации и ограничение полезности, есть ли решение с утилитой, большей или равной этой границе » (или слегка модифицированной для задачи минимизации).

Я также предполагаю , что NP вы имеете в виду (гипотетический) часть НП , которая не является частью P . Если P = NP , конечно, NP-полная все еще существует, но она будет равна P (совпадает только с P для некоторых понятий редукции, таких как многозначное сокращение за полиномиальное время с помощью @ AndrásSalamon), что не так впечатляет ( и уменьшит " пробел ", который вы указали в своем вопросе).

Я все чаще замечаю, что большинство дискретных задач являются NP-полными.

Теперь, когда мы разобрались , что из: Есть много проблем оптимизации , которые находятся в P : кратчайшего пути проблемы , максимально проблемы потока (для интегральных мощностей), минимального остовного дерева и максимального соответствия . Хотя эти проблемы могут показаться вам «тривиальными для решения», они все еще остаются проблемами оптимизации, и во многих случаях конструкция (и подтверждение правильности) не так проста. Таким образом, претензия не содержит все дискретные проблемы, являющиеся NP-полными. Поскольку P не равно NP , эти проблемы не могут быть NP-полными .

$\Sigma^P_i$

Принимая во внимание, что оптимизация постоянных проблем почти всегда легко достижима.

Популярной непрерывной проблемой, которая является NP-трудной, является квадратичное программирование .

$\vec{x}$

На самом деле линейное программирование уже давно считается NP-сложным , но с очень хорошо работающей эвристикой ( метод Simplex ). Алгоритм Кармаркара Однако в P .

С того момента, как проблема оптимизации имеет дело с невыпуклыми объектами, в общем случае будет трудно - если не невозможно - найти эффективный алгоритм.

Список используемой литературы

[1] Сложность вычислений, современный подход , Санджив Арора и Боаз Барак