# Stochastic version of a strongly NP-Complete problem

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?

-
Are you interested in the vehicle routing problem or the general question ? –  Suresh Venkat Dec 23 '12 at 21:22
The answer to the vehicle routing problem would do for now.Although,having the answer to the wider question would be great. –  Shalabh Vidyarthi Dec 23 '12 at 22:55
Please clarify what you mean by "stochastic". –  Yoshio Okamoto Dec 24 '12 at 23:29

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