Задачи оптимизации с хорошей характеристикой, но без алгоритма полиномиального времени

23

Рассмотрим задачи оптимизации следующего вида. Пусть f(x) - вычислимая функция полиномиального времени, которая отображает строку x в рациональное число. Задача оптимизации заключается в следующем: что максимальное значение f(x) над n -битовый строки x ?

gxnymnm

maxxf(x)=minyg(y)
xnymnm

Многочисленные естественные и важные задачи оптимизации имеют такую ​​минимаксную характеристику. Несколько примеров (теоремы, на которых основаны характеристики, показаны в скобках):

Линейное программирование (LP Duality Thm), максимальный поток (Max Flow Min Cut Thm), Max Bipartite Matching (Konig-Hall Thm), Max Non-Bipartite Matching (Tutte's Thm, формула Tutte-Berge), Max Disjoint Arborescences в ориентированном графе ( Edmond's Disjoint Branching Thm), Максимальная упаковка связующего дерева в неориентированном графе (Thm Упаковка дерева Tutte), Минимальное покрытие лесами (Нэш-Уильямс Thm), Максимальная упаковка направленного разреза (Lucchesi-Younger Thm), Максимальное пересечение 2-матроидов (пересечение Matroid Thm), Макс непересекающиеся пути (Thm Менгера), Макс Антикхайн в «Частично заказанном наборе» (Dilworth Thm) и многие другие.

Во всех этих примерах алгоритм полиномиального времени также доступен, чтобы найти оптимальный. Мой вопрос:

Есть ли какая-либо проблема оптимизации с минимаксной характеристикой, для которой до сих пор не было найдено алгоритма полиномиального времени?

Примечание: линейное программирование находилось в этом состоянии около 30 лет!

Андрас Фараго
источник

Ответы:

22

В каком - то техническом смысле вы спрашиваете , является ли . Предположим , что L N P C O N P , таким образом , существует поли-времени , F и G , так что х L тогда и только тогда у : Р ( х , у ) и х L тогда и только тогда у : G ( х , у )P=NPcoNPLNPcoNPFGxLy:F(x,y)xLy:G(x,y), Это может быть преобразовано в характеристику minmax как если F ( x , y ) и f x ( y ) = 0 в противном случае; g x ( y ) = 0, если G ( x , y ) и g x ( y ) = 1 в противном случае. Теперь на самом деле мы т а х у п (fx(y)=1F(x,y)fx(y)=0gx(y)=0G(x,y)gx(y)=1maxyfx(y)=minygx(y) .

Таким образом, в этом смысле любая проблема, о которой известно, что она находится в но о которой неизвестно, что она находится в P, может быть превращена в ответ на ваш вопрос. Например, Факторинг (скажем, версия решения о том, является ли i -й бит наибольшего множителя 1).NPcoNPPi

Ноам
источник
9
У меня сложилось впечатление, что некоторые люди даже зашли так далеко, что приняли как определение «хорошей характеристики». NPcoNP
Джошуа Грохов
И для списка таких проблем, см. Mathoverflow.net/questions/31821/…
Рахул Савани
14

Сеймур и Томас показали минимальную характеристику ширины дерева. Тем не менее, ширина дерева NP-трудна. Это, однако, не совсем та характеристика, о которой вы просите, потому что двойная функция не является вычисляемой за полиномиальное время функцией короткого сертификата. Это, скорее всего, неизбежно для проблем с завершением NP, потому что в противном случае у нас была бы проблема с NP-завершением в coNP, что подразумевало бы коллапс NP = coNP, и я бы посчитал это шоком.g

The treewidth of a graph G is equal to the smallest smallest width of a tree decomposition of G. A tree decomposition of a graph G is a tree T such that each vertex x of T is labeled by a set S(x) of vertices of G with the property:

  1. For all xV(T), |S(x)|k+1.
  2. Объединение всех представляет собой множество вершин G .S(x)G
  3. Для любого подграф T, индуцированный всеми x, для которых u S ( x ) , связен.uV(G)TxuS(x)
  4. Каждое ребро является подмножеством некоторого S ( x ) для x V ( T ) .(u,v)E(G)S(x)xV(T)

Seymour and Thomas showed that treewidth is equal to bramble number of G: the maximum k such that there is a collection of connected subgraphs of G so that:

  1. Each two subgraphs are intersecting or connected by an edge.
  2. No set of k vertices of G hits all subgraphs.

Such a collection of subgraphs is called a bramble of order k

Notice how "bramble number is at least k" is a statement, with both quantifiers over exponentially large sets. So it does not suggest an easy to verify certificate (and if there were one that would be really big news, as I said above). To make things even worse, Grohe and Marx showed that for every k there is a graph of treewidth k such that any bramble of order at least k1/2+ϵ must consist of exponentially many subgraphs. They also show that there exist brambles of order k1/2/O(log2k) of polynomial size.

Sasho Nikolov
источник
1
Thank you, it is a very nice example, even if it does not fall in the category I am looking for. It is interesting to note that this min-max theorem about the treewidth was published in 1993, and at that time the NP-completeness of treewidth was already known. Therefore, the result could have served as a reason to conjecture NP=coNP. While the exponential lower bound on the bramble size terminally disqualified it for that role, this lower bound was only published 16 years later.
Andras Farago
Andras, at the time it also known that hitting set is NP-hard in general (it was one of Karp's 21 problems). So even with polynomial size brambles, computing the order is not easy, unless you can somehow use the structure of brambles. Still, it is interesting that the size of brambles was not investigated earlier.
Sasho Nikolov
13

Parity games, Mean-payoff games, Discounted games, and Simple Stochastic games fall within this category.

All of them are infinite two-player zero-sum games played on graphs, where players control vertices and choose where a token should go next. All have equilibria in memoryless positional strategies, meaning that each player chooses an edge at each choice vertex deterministically and irrespective of the history of play. Given a strategy of one player, a best response of the other player can be computed in polynomial time, and the min-max relationship you require holds for the "value" of the game.

The natural decision variants of these problems are in NP and co-NP (indeed UP and co-UP) and the function problems, to find an equilibrium, lie in PLS and PPAD.

The algorithms with best-known running time are sub-exponential, but super-polynomial (e.g. O(nn), where n is the number of vertices in the game graph).

See, e.g.,

David S. Johnson. 2007. The NP-completeness column: Finding needles in haystacks. ACM Trans. Algorithms 3, 2, Article 24 (May 2007). DOI=10.1145/1240233.1240247 http://doi.acm.org/10.1145/1240233.1240247

Rahul Savani
источник