<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-22T17:57:02.453Z
2011-03-22T17:57:02.453Z
Aaron Roth
<p>Consider a minimax problem of the form:</p>

<p>$\min_{x\in X} \max_{u\in U} f(x,u)$</p>

<p>The outer problem $\min_{x\in X} f(x,u)$ for any given $u$ is polynomially solvable.</p>

<p>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?</p>

CC BY-SA 2.5
2011-03-22T11:37:54.620Z
Isn't it obvious that if the entire problem is in P then the inner problem is also in P?
Zirui Wang
CC BY-SA 2.5
2011-03-22T13:46:32.980Z
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.
Aaron Roth
CC BY-SA 2.5
2011-03-22T14:06:14.697Z
@Aaron: Your comment also answers the question or not?
Marc Bury
CC BY-SA 2.5
2011-03-22T14:11:56.110Z
@Marc: I do think so, by slightly modifying $f(0,u) = \phi(u)$.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-03-22T17:50:52.523Z
@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.
Aaron Roth
CC BY-SA 2.5
2011-03-22T22:13:12.457Z
@Aaron: In your version the min-max value is $0$ so it doesn't matter whether $\phi$ is satisfiable or not.
Marc Bury
CC BY-SA 2.5
2011-03-22T23:16:42.707Z
@Marc: Right! Thats why the problem is in P. On the other hand, fixing x = 1, the inner problem is NP hard.
Aaron Roth
CC BY-SA 2.5
2011-03-23T00:50:02.557Z
Ah, I see, sorry for the confusing comment. But I guess the problem is that it's hard to decide whether it is 0 or 1? (Since the min always takes x = 0.)
Hsien-Chih Chang 張顯之
<cc.complexity-theory><optimization>
Is minimax problem NP-Hard when the inner problem is NP-Hard ?
Chang
# Is minimax problem NP-Hard when the inner problem is NP-Hard ?

(Asked by: username_0 on 2011-03-22)

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?

**Tags:** cc.complexity-theory, optimization

> **Comments:**
> **username_1**: Isn't it obvious that if the entire problem is in P then the inner problem is also in P?  
> **username_2**: 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.  
> **username_3**: @Aaron: Your comment also answers the question or not?  
> **username_4**: @Marc: I do think so, by slightly modifying $f(0,u) = \phi(u)$.  
> **username_2**: @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.  
> **username_3**: @Aaron: In your version the min-max value is $0$ so it doesn't matter whether $\phi$ is satisfiable or not.  
> **username_2**: @Marc: Right! Thats why the problem is in P. On the other hand, fixing x = 1, the inner problem is NP hard.  
> **username_4**: Ah, I see, sorry for the confusing comment. But I guess the problem is that it's hard to decide whether it is 0 or 1? (Since the min always takes x = 0.)  

---

## 1 answers

### Answer by username_2 on 2011-03-22. Score: 13 | Accepted answer

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.


---

