This paper explores the computational complexity of decentralized control in Markov decision processes (MDPs) and partially observable Markov decision processes (POMDPs). The authors introduce two models: decentralized POMDP (DEC-POMDP) and decentralized MDP (DEC-MDP), which generalize MDP and POMDP to allow for decentralized control by multiple agents. These models are shown to be complete for the complexity class nondeterministic exponential time (NEXP), indicating that solving these problems is significantly more computationally intensive than solving centralized problems. The results suggest that decentralized planning problems cannot be easily reduced to centralized ones and solved using established techniques. The paper also discusses the implications of these complexity results for the design of algorithms for decentralized planning. The authors show that the DEC-POMDP problem is NEXP-complete for m ≥ 2 agents, and the DEC-MDP problem is NEXP-complete for m ≥ 3 agents. These results highlight the fundamental differences between centralized and decentralized control of Markov processes. The paper also discusses the implications of these results for the development of algorithms for decentralized planning and the challenges of solving decentralized planning problems.This paper explores the computational complexity of decentralized control in Markov decision processes (MDPs) and partially observable Markov decision processes (POMDPs). The authors introduce two models: decentralized POMDP (DEC-POMDP) and decentralized MDP (DEC-MDP), which generalize MDP and POMDP to allow for decentralized control by multiple agents. These models are shown to be complete for the complexity class nondeterministic exponential time (NEXP), indicating that solving these problems is significantly more computationally intensive than solving centralized problems. The results suggest that decentralized planning problems cannot be easily reduced to centralized ones and solved using established techniques. The paper also discusses the implications of these complexity results for the design of algorithms for decentralized planning. The authors show that the DEC-POMDP problem is NEXP-complete for m ≥ 2 agents, and the DEC-MDP problem is NEXP-complete for m ≥ 3 agents. These results highlight the fundamental differences between centralized and decentralized control of Markov processes. The paper also discusses the implications of these results for the development of algorithms for decentralized planning and the challenges of solving decentralized planning problems.