<p>A first observation is that the stochastic version of an optimization problem will always be <em>at least as hard</em> as the deterministic version, since fixed constant values in an optimization instance are degenerate special cases of random-variable values.</p>

<p>Now to understand the computational complexity of stochastic optimization problems in more detail, it's important first to explicitly define the "order of quantification" for the problem, and also the measure of "success."</p>

<p>Suppose $x = (x_1, x_2, \ldots, , x_n)$ are the variables to be set by the optimizing party, and $r = (r_1, \ldots, r_m)$ are the "stochastic" variables.  For simplicity of discussion, let's assume these variables are all Boolean.  Let $F(x, r): \{0, 1\}^{n + m} \rightarrow [0, 1]$ be the objective function we want to maximize.  </p>

<p>The $r_i$'s are going to be set uniformly at random by Nature, let's assume.  But, are these variables set before the optimizer's decision, or after?  Or, are the optimizer's decisions "interlaced" with the random settings?  </p>

<p>(I'm assuming that in whatever model we use, the optimizer can at least "see" the random settings that have already been made by Nature.)</p>

<p>The different possibilities described above can be denoted concisely as</p>

<p>(O1)  $[x_1, \ldots, x_n, r_1, \ldots, r_m]$ (optimizer moves first);</p>

<p>(O2)  $[r_1, \ldots, r_m, x_1, \ldots, x_n]$ (nature moves first);</p>

<p>(O3)  $[x_1, r_1, x_2, r_2, \ldots, x_n, r_n, r_{n + 1}, \ldots, r_{m}]$  (alternation; assuming here that $m \geq n$).</p>

<p>So that's the "quantification order" question.  Next, we also have to decide how to measure the "success" of an optimizer's strategy.  There are two simple possibilities:</p>

<p>(S1)  Measure success as the <em>expected</em> output value of $F(x, r)$;</p>

<p>(S2)  Measure success as the probability that $F(x, r)$ meets or exceeds a desired threshold value $\alpha \in [0, 1]$.  </p>

<p>To make my life easier, I'm only going to discuss (S1), but most of what I say also applies to (S2).</p>

<p>Finally, we have the issue of what kind of function $F$ is.  There are two fairly general options to consider:</p>

<p>(C1)  $F$ is a general poly-time computable function into $[0, 1]$;</p>

<p>(C2)  $F$ is defined by a collection of local Boolean constraints $\psi_1, \ldots, \psi_\ell$, each acting on $O(1)$ variables in $(x, r)$, and $F(x, r)$ equals the fraction of satisfied constraints.</p>

<p>OK, now having multiplied the number of questions to consider, I can at least answer some of them.  First, if one is asking for extremely accurate information about the achievable success, then the problem becomes ridiculously hard, even if there are no optimization variables!  (i.e., even if x is empty.)  For instance, if $F(r)$ is a SAT instance outputting 0 or 1 according to whether it is satisfied, then (S1) asks us to compute the fraction of accepting inputs, which is $\# P$-complete.  So I think it is more reasonable to settle for a .001-approximation (accurate to within $\pm .001$), or maybe more ambitiously for a $1/n^c$-approximation to the success measure, for each $c &gt; 0$.  Now with these goals in mind:</p>

<p>-For (O1), in which the optimizer sets all the $x$-variables first, the problem is $MA$-complete to .001-approximate, if $F$ is a general Ptime-computable function.  (One has to define completeness for an approximation problem appropriately, and for the promise class $MA$, but morally this is the right complexity classification.)  The proof just follows the definitions.  If $F$ is as in (C2), then the problem is in $NP$, since we can use linearity of expectations to compute the expected value of $F(x, r)$ for any fixed $x$.</p>

<p>-For (O2), in which Nature sets the $r$-variables first, the problem is $AM$-complete to .001-approximate, whether $F$ is as in (C1) or (C2).  For (C1) this follows from an easy black-box application of the Cook's theorem plus the PCP theorem.  For (C2), I showed the $AM$-completeness result in the following paper:</p>

<p><a href="http://eccc.hpi-web.de/report/2010/019/">http://eccc.hpi-web.de/report/2010/019/</a></p>

<p>-For (O3), interlaced variable-settings, the problem is $PSPACE$-complete to .001-approximate, even in the (C2) case; this was shown by Condon, Feigenbaum, Lund, and Shor in this paper:</p>

<p><a href="http://cs-www.cs.yale.edu/homes/jf/CFLS.pdf">http://cs-www.cs.yale.edu/homes/jf/CFLS.pdf</a></p>

<p>Hope this is helpful...</p>

CC BY-SA 3.0
2012-12-25T05:24:48.317Z
excellent answer ! btw in the (O1)/(C2) case, do you mean "any fixed x" ?
Suresh Venkat
CC BY-SA 3.0
2012-12-25T19:44:09.493Z
Yes--fixed, thanks!
Andy Drucker
CC BY-SA 3.0
2012-12-25T02:50:55.947Z
2012-12-25T19:43:46.667Z
2012-12-25T19:43:46.667Z
Andy Drucker
<p>Does a strongly NP-Complete problem remain strongly NP-Complete if the variable set on which the objective/cost function depends are made stochastic ? 
The problem Tree CVRP(Capacitated Vehicle Routing Problem) is proven to be strongly NP-Complete by Hamaguchi &amp; Katoh (1998)( <a href="http://bit.ly/VdUBDz" rel="nofollow">http://bit.ly/VdUBDz</a> ). If the demands are made stochastic then does the problem remain strongly NP-Complete?</p>

CC BY-SA 3.0
2012-12-23T21:22:38.007Z
Are you interested in the vehicle routing problem or the general question ?
Suresh Venkat
CC BY-SA 3.0
2012-12-23T22:55:25.953Z
The answer to the vehicle routing problem would do for now.Although,having the answer to the wider question would be great.
Shalabh Vidyarthi
CC BY-SA 3.0
2012-12-24T23:29:02.457Z
Please clarify what you mean by "stochastic".
Yoshio Okamoto
<cc.complexity-theory><reference-request><optimization>
Stochastic version of a strongly NP-Complete problem
Shalabh Vidyarthi
# Stochastic version of a strongly NP-Complete problem

(Asked by: username_0 on 2012-12-23)

Does a strongly NP-Complete problem remain strongly NP-Complete if the variable set on which the objective/cost function depends are made stochastic ?
The problem Tree CVRP(Capacitated Vehicle Routing Problem) is proven to be strongly NP-Complete by Hamaguchi & Katoh (1998)( <http://bit.ly/VdUBDz> ). If the demands are made stochastic then does the problem remain strongly NP-Complete?

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

> **Comments:**
> **username_1**: Are you interested in the vehicle routing problem or the general question ?  
> **username_0**: The answer to the vehicle routing problem would do for now.Although,having the answer to the wider question would be great.  
> **username_2**: Please clarify what you mean by "stochastic".  

---

## 1 answers

### Answer by username_3 on 2012-12-25. Score: 10

A first observation is that the stochastic version of an optimization problem will always be *at least as hard* as the deterministic version, since fixed constant values in an optimization instance are degenerate special cases of random-variable values.

Now to understand the computational complexity of stochastic optimization problems in more detail, it's important first to explicitly define the "order of quantification" for the problem, and also the measure of "success."

Suppose $x = (x\_1, x\_2, \ldots, , x\_n)$ are the variables to be set by the optimizing party, and $r = (r\_1, \ldots, r\_m)$ are the "stochastic" variables. For simplicity of discussion, let's assume these variables are all Boolean. Let $F(x, r): \{0, 1\}^{n + m} \rightarrow [0, 1]$ be the objective function we want to maximize.

The $r\_i$'s are going to be set uniformly at random by Nature, let's assume. But, are these variables set before the optimizer's decision, or after? Or, are the optimizer's decisions "interlaced" with the random settings?

(I'm assuming that in whatever model we use, the optimizer can at least "see" the random settings that have already been made by Nature.)

The different possibilities described above can be denoted concisely as

(O1) $[x\_1, \ldots, x\_n, r\_1, \ldots, r\_m]$ (optimizer moves first);

(O2) $[r\_1, \ldots, r\_m, x\_1, \ldots, x\_n]$ (nature moves first);

(O3) $[x\_1, r\_1, x\_2, r\_2, \ldots, x\_n, r\_n, r\_{n + 1}, \ldots, r\_{m}]$ (alternation; assuming here that $m \geq n$).

So that's the "quantification order" question. Next, we also have to decide how to measure the "success" of an optimizer's strategy. There are two simple possibilities:

(S1) Measure success as the *expected* output value of $F(x, r)$;

(S2) Measure success as the probability that $F(x, r)$ meets or exceeds a desired threshold value $\alpha \in [0, 1]$.

To make my life easier, I'm only going to discuss (S1), but most of what I say also applies to (S2).

Finally, we have the issue of what kind of function $F$ is. There are two fairly general options to consider:

(C1) $F$ is a general poly-time computable function into $[0, 1]$;

(C2) $F$ is defined by a collection of local Boolean constraints $\psi\_1, \ldots, \psi\_\ell$, each acting on $O(1)$ variables in $(x, r)$, and $F(x, r)$ equals the fraction of satisfied constraints.

OK, now having multiplied the number of questions to consider, I can at least answer some of them. First, if one is asking for extremely accurate information about the achievable success, then the problem becomes ridiculously hard, even if there are no optimization variables! (i.e., even if x is empty.) For instance, if $F(r)$ is a SAT instance outputting 0 or 1 according to whether it is satisfied, then (S1) asks us to compute the fraction of accepting inputs, which is $\# P$-complete. So I think it is more reasonable to settle for a .001-approximation (accurate to within $\pm .001$), or maybe more ambitiously for a $1/n^c$-approximation to the success measure, for each $c > 0$. Now with these goals in mind:

-For (O1), in which the optimizer sets all the $x$-variables first, the problem is $MA$-complete to .001-approximate, if $F$ is a general Ptime-computable function. (One has to define completeness for an approximation problem appropriately, and for the promise class $MA$, but morally this is the right complexity classification.) The proof just follows the definitions. If $F$ is as in (C2), then the problem is in $NP$, since we can use linearity of expectations to compute the expected value of $F(x, r)$ for any fixed $x$.

-For (O2), in which Nature sets the $r$-variables first, the problem is $AM$-complete to .001-approximate, whether $F$ is as in (C1) or (C2). For (C1) this follows from an easy black-box application of the Cook's theorem plus the PCP theorem. For (C2), I showed the $AM$-completeness result in the following paper:

<http://eccc.hpi-web.de/report/2010/019/>

-For (O3), interlaced variable-settings, the problem is $PSPACE$-complete to .001-approximate, even in the (C2) case; this was shown by Condon, Feigenbaum, Lund, and Shor in this paper:

<http://cs-www.cs.yale.edu/homes/jf/CFLS.pdf>

Hope this is helpful...

> **Comments:**
> **username_1**: excellent answer ! btw in the (O1)/(C2) case, do you mean "any fixed x" ?  
> **username_3**: Yes--fixed, thanks!  

---

