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

27

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

alekdimi
источник
14
Конечно, их много. Двухстороннее и общее согласование, и минимальные разрезы являются тремя классическими полиномиальными временными дискретными задачами. Многие непрерывные невыпуклые задачи оптимизации NP-трудны: найти диаметр выпуклого множества или вычислить инъективную норму трехмерного тензора.
Сашо Николов
6
Вот простая задача непрерывной оптимизации, которую трудно решить NP
Юкка Суомела
8
Я не уверен, какие проблемы вы имеете в виду, но многие непрерывные проблемы, которые «решаются» градиентными методами, на самом деле не «решаются»: метод просто находит какой-то локальный оптимум.
Суреш Венкат
1
Все ответы до сих пор кажутся контрпримерами, но было бы неплохо увидеть некоторые случаи, когда это правило кажется верным. Два, которые приходят на ум, это линейное программирование против целочисленного программирования и выпуклая оптимизация против субмодулярной максимизации.
Усул
13
Я думаю, что вся дискретная и непрерывная вещь - красная сельдь. Проблема должна иметь особую структуру, чтобы быть эффективно решаемой. Я думаю, что реальная разница здесь заключается в том, что в случае простых непрерывных задач специальная структура имеет тенденцию быть выпуклой, в то время как в случае простых дискретных задач все выглядит сложнее: иногда структура является субмодулярностью или пересечением матроида, но часто это не так. Вероятно, это связано с тем, что мы еще не очень хорошо понимаем дискретную математику.
Сашо Николов

Ответы:

41

Пример, который мне нравится, - это проблема, когда при различных решить, что: π - π cos ( a 1 z ) cos ( a 2 z ) cos ( a n z )a1,a2,,anN

ππcos(a1z)cos(a2z)cos(anz)dz0

{a1,,an}

n

Джо Бебель
источник
4
Поскольку мы находимся на этой теме, самая ранняя ссылка на эту проблему, которую я могу найти, находится в «Природе вычислений» Мура и Мертенса. Они не дают никаких ссылок, поэтому я предполагаю, что либо они изобрели, либо это происходит из фольклора. Буду признателен, если кто-то знает источник этой проблемы.
Джо Бебель
nn
1
nn
3
По-видимому, первоначальный источник этой проблемы: Дэвид Плейстед. Некоторые проблемы делимости многочленов и целых чисел являются NP-трудными. SIAM Journal of Computing, 7 (4): 458–464, 1978. Ссылка находится в задней части Мура и Мертенса, но не в самом тексте.
Джо Бебель
26

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

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

Дэвид Эппштейн
источник
1
«Кратчайший путь среди многогранных препятствий» непрерывен только по названию, не так ли? Мы можем представить пространство конфигурации как объединение нескольких отдельных частей, соответствующих путям, которые «обнимают» данный набор препятствий; тогда локальная оптимизация в каждом данном фрагменте (т. е. в любом данном наборе препятствий) проста, но решить, какой из путей имеет наилучшее в мире расстояние, является трудной частью проблемы.
Стивен Стадницки
13

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

A={a1,a2,,am}B={b1,b2,,bn}i=1maij=1nbjжесткий, широко распространено подозрение, что он может быть NP-сложным и может фактически быть за пределами NP (как отмечалось в комментариях, есть веские основания полагать, что он не является NP-завершенным); единственное известное на сегодняшний день ограничение - это несколько уровней выше полиномиальной иерархии. Очевидно, что представление этой проблемы настолько дискретно, насколько это возможно - набор целых чисел и вопрос «да / нет» о них - но проблема возникает потому, что, хотя вычисление квадратных корней с любой заданной точностью является простой задачей, их, возможно, потребуется вычислить с высокой (потенциально суперполиномиальной) точностью, чтобы решить неравенство тем или иным способом. Это «дискретная» проблема, которая возникает в удивительном количестве оптимизационных контекстов и помогает внести свой вклад в их собственную сложность.

Стивен Стадницки
источник
4
Мне также очень нравится этот пример, хотя стоит отметить, что есть веские основания полагать, что он не является NP-завершенным; см. ( cstheory.stackexchange.com/a/4010/8985 )
Джо Бебель
@JoeBebel Очень хороший момент - я немного изменил свой язык, чтобы отразить это. Спасибо!
Стивен Стадницки
6

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

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

Mehrdad
источник
Я думаю, что дискретность также является частью проблемы. Скажем, например, у вас был бы ILP-варант LP. Например, вы можете стремиться найти решение для варианта LP, но тогда есть еще 2^n« интересные соседи », которые нужно искать.
Виллем Ван Онсем
@CommuSoft: Не совсем ... дискретность не в этом. Проверьте кратчайший путь проблема , которая является дискретной проблемой , но тем не менее , сводится к частному случаю интегрального линейного программирования , который является Р-времени разрешимы (не следует путать с целочисленного линейного программирования , который, очевидно , NP-трудной).
Мердад
в этом нет ничего удивительного: поскольку целочисленное линейное программирование является NP-полным, каждая задача в P (которая может быть решена за много времени) может быть преобразована за много времени в задачу ILP.
Виллем Ван Онсем
@CommuSoft: Вы прочитали комментарий полностью? Я не говорю о ILP.
Мердад
извини, читай быстро. Но все же это потому, что ограничения являются полностью унимодулярными , поэтому только благодаря «милости» хорошо структурированных ограничений такие проблемы легко решаемы. В целом, дискретизация - проблемный аспект проблем.
Виллем Ван Онсем,
5

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

Сначала несколько определений: большинство проблем оптимизации не являются частью 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-полными .

ΣiP

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

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

x

xTQx2+cTx

Axb

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

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

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

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

Виллем Ван Онсем
источник
2
Определения параграфа действительно запутаны. Рюкзак - это проблема оптимизации NP. Неверно, что «неизвестно», если версия оптимизации находится в NP: это не так, просто по определению. Кроме того, я не думаю, что мы знаем, что любая проблема, которая является NP-полной, если NP не равна PIe 3-SAT, будет NP-полной, даже если P = NP (фактически, если P = NP, каждая проблема в P является NP-полной).
Сашо Николов
@ AndrásSalamon: точка взята. Я удалил эту часть. Это было действительно немного небрежно.
Виллем Ван Онсем
@ AndrásSalamon: очевидно, это правда. Поэтому он говорит: « Учитывая , P не равно NP, эти проблемы , таким образом , не может быть NP-полной. »
Willem Van Onsem
@ AndrásSalamon: Хорошо, если P=NPкаждая задача в NP-полной является по определению частью NP и, следовательно, расширением P , теперь P означает, что существует полиномиальный алгоритм. Дело в том, я думаю, что преобразование не имеет значения, потому что для каждого языка в P должен существовать полиномиальный алгоритм. Независимо от того, берете ли вы (в большинстве случаев полиномиальное) преобразование или нет, это не имеет значения. Остается многочлен, таким образом , в P . Другими словами, поскольку исходный элемент находится в P , вы можете использовать любое преобразование многовременности бесплатно (не приводя к более высокому классу сложности).
Виллем Ван Онсем
2
Рюкзак как проблема оптимизации, конечно, не является NP-завершенным, потому что это не проблема решения, то есть не в NP. В любом случае, я понимаю, что вы говорите, но я думаю, что такие подробности уровня старшекурсников следует принимать на должном уровне на форуме исследовательского уровня, например CStheory @ SE, так же, как я не ожидаю увидеть объяснение. о том, как сходимость по вероятности не совпадает с почти наверняка сходимостью по Mathoverflow.
Сашо Николов