Optimization problems with minimax characterization, but no polynomial-time algorithm

Question

Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the maximum value of $f(x)$ over $n$-bit strings $x$?

Let us say that such a problem has a minimax characterization, if there is another polynomial-time computable function $g$, such that $$\max_x f(x) = \min_y g(y)$$ holds. Here $x$ runs over all $n$-bit strings, and $y$ runs over all $m$-bit strings; $n$ and $m$ may be different, but they are polynomially related.

Numerous natural and important optimization problems have such minimax characterization. A few examples (the theorems on which the characterizations are based shown in parenthesis):

Linear Programming (LP Duality Thm), Maximum Flow (Max Flow Min Cut Thm), Max Bipartite Matching (Konig-Hall Thm), Max Non-Bipartite Matching (Tutte's Thm, Tutte-Berge formula), Max Disjoint Arborescences in directed graph (Edmond's Disjoint Branching Thm), Max Spanning Tree Packing in undirected graph (Tutte's Tree Packing Thm), Min Covering by Forests (Nash-Williams Thm), Max Directed Cut Packing (Lucchesi-Younger Thm), Max 2-Matroid Intersection (Matroid Intersection Thm), Max Disjoint Paths (Menger's Thm), Max Antichain in Partially Ordered Set (Dilworth Thm), and many others.

In all these examples, a polynomial-time algorithm is also available to find the optimum. My question:

Is there any optimization problem with a minimax characterization, for which no polynomial-time algorithm has been found so far?

Note: Linear Programming was in this status for about 30 years!

Answer 1

In some technical sense you are asking whether $P = NP \cap coNP$. Suppose that $L \in NP \cap coNP$, thus there exists poly-time $F$ and $G$ so that $x \in L$ iff $\exists y: F(x,y)$ and $x \not\in L$ iff $\exists y: G(x,y)$. This can be recast as a minmax characterization by $f_x(y) = 1$ if $F(x,y)$ and $f_x(y) = 0$ otherwise; $g_x(y) = 0$ if $G(x,y)$ and $g_x(y) = 1$ otherwise. Now indeed we have $max_y f_x(y) = min_y g_x(y)$.

So in this sense, any problem known to be in $NP \cap coNP$ but not known to be in $P$ can be turned into an answer to your question. E.g. Factoring (say, the decision version of whether the $i$'th bit of the largest factor is 1).

Answer 2

Seymour and Thomas showed a min-max characterization of treewidth. Yet, tree width is NP-hard. This however is not quite the kind of characterization you are asking for, because the dual function $g$ is not a polynomial time computable function of a short certificate. This is most likely unavoidable for NP complete problems, because otherwise we would have an NP-complete problem in coNP, implying a collapse NP = coNP, and I would consider that quite the shocker.

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 $x \in V(T)$, $|S(x)| \leq k+1$.
2. The union of all $S(x)$ is the vertex set of $G$.
3. For every $u \in V(G)$, the subgraph of $T$ induced by all $x$ for which $u \in S(x)$ is connected.
4. Every edge $(u, v) \in E(G)$ is a subset of some $S(x)$ for $x \in V(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 $\exists\forall$ 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 $k^{1/2 + \epsilon}$ must consist of exponentially many subgraphs. They also show that there exist brambles of order $k^{1/2}/O(\log^2 k)$ of polynomial size.

Answer 3

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(n^\sqrt{n})$, 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