Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
3  
Please clarify what you mean by "stochastic". –  Yoshio Okamoto Dec 24 '12 at 23:29

1 Answer 1

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

share|improve this answer
2  
excellent answer ! btw in the (O1)/(C2) case, do you mean "any fixed x" ? –  Suresh Venkat Dec 25 '12 at 5:24
    
Yes--fixed, thanks! –  Andy Drucker Dec 25 '12 at 19:44
    
Thanks for the answer. –  Shalabh Vidyarthi Dec 27 '12 at 1:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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