Рассмотрим задачи оптимизации следующего вида. Пусть - вычислимая функция полиномиального времени, которая отображает строку в рациональное число. Задача оптимизации заключается в следующем: что максимальное значение над -битовый строки ?
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 лет!
Сеймур и Томас показали минимальную характеристику ширины дерева. Тем не менее, ширина дерева NP-трудна. Это, однако, не совсем та характеристика, о которой вы просите, потому что двойная функция не является вычисляемой за полиномиальное время функцией короткого сертификата. Это, скорее всего, неизбежно для проблем с завершением NP, потому что в противном случае у нас была бы проблема с NP-завершением в coNP, что подразумевало бы коллапс NP = coNP, и я бы посчитал это шоком.g
The treewidth of a graphG 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:
Seymour and Thomas showed that treewidth is equal to bramble number ofG : the maximum k such that there is a collection of connected subgraphs of G so that:
Such a collection of subgraphs is called a bramble of orderk
Notice how "bramble number is at leastk " 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.
источник
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
источник