Consider a minimax problem of the form:$\min_{x\in X} \max_{u\in U} f(x,u)$The outer problem $\min_{x\in X} f(x,u)$ for any given $u$ is polynomially solvable.If the inner problem $\max_{u\in U} f(x,u)$ for any given $x$ is NP-Hard, is the entire problem also NP-Hard?
Is minimax problem NP-Hard when the inner problem is NP-Hard ?
cc.complexity theory;optimization
The answer to your question is no, although for natural problems that you might be thinking about, it may be a good heuristic that if the inner problem is NP hard, the whole problem is probably hard as well. But you can come up with the following contrived counterexample.Let $X = \{0,1\}$ and $U = \{0,1\}^n$, and let $\phi$ and $\theta$ be two 3SAT instances with the promise that exactly one of them is satisfiable. Let $f(0,u) = \phi(u)$ and let $f(1,u) = \theta(u)$. Then the minmax value is always 0, so computing it is in P, but for any fixed $x$, the problem is 3SAT and is NP hard.