I have a stochastic dynamic programming problem, the deterministic version can be solved in polynomial time. I'd like to show this stochastic problem is NP-hard and even Approximation-hard: e.g., with a maximization objective, there is a constant $\alpha_0$, for any $\alpha > \alpha_o$, if there is a $\alpha$-approximation algorithm for this stochastic problem (i.e., recover at least $\alpha$ fraction of the optimal expected objective), then P = NP.I was wondering if there is some related literature that deals with similar problems for me to refer to? Most NP-hard and Approximation-hard problems I've learned from textbooks are static problems. I'm still thinking of how to reduce a static problem to a stochastic dynamic problem.
Stochastic dynamic programming problem that is Approximation-hard
cc.complexity theory;co.combinatorics;approximation algorithms;approximation hardness