POMDP - Hard problems.
Computing an infinite (polynomial) horizon undiscounted optimal strategy for a deterministic POMDP is P-space-hard (NP-complete) [PT,L].
Computing an infinite (polynomial) horizon undiscounted optimal strategy for a stochastic POMDP is EXPTIME-hard (P-space-complete) [PT,L].
Computing an infinite (polynomial) horizon undiscounted optimal policy for an MDP is P-complete [PT] .