6
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\begingroup$ Isn't it obvious that if the entire problem is in P then the inner problem is also in P? $\endgroup$
    – Zirui Wang
    Commented Mar 22, 2011 at 11:37
  • 4
    $\begingroup$ Zirui: I don't think thats the case. Suppose $f(0, u) = 0$, but $f(1, u) = 1 + \phi(u)$, where $\phi(u) = 1$ if and only if $u$ is a satisfying assignment to some 3sat instance $\phi$. Then the entire problem is in $P$, because the answer is 0 (set $x = 0$), but the inner problem is NP hard because it is equivalent to 3SAT. $\endgroup$
    – Aaron Roth
    Commented Mar 22, 2011 at 13:46
  • $\begingroup$ @Aaron: Your comment also answers the question or not? $\endgroup$
    – Marc Bury
    Commented Mar 22, 2011 at 14:06
  • $\begingroup$ @Marc: I do think so, by slightly modifying $f(0,u) = \phi(u)$. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Mar 22, 2011 at 14:11
  • $\begingroup$ @Marc: No, my comment (and even Hsien-Chih's modification) does not answer the question. In Hsien-Chih's version, it is still hard to determine whether the min-max value is 1 or 2. $\endgroup$
    – Aaron Roth
    Commented Mar 22, 2011 at 17:50

1 Answer 1

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.