The paper "The Complexity of Decentralized Control of Markov Decision Processes" by Daniel S. Bernstein, Shlomo Zilberstein, and Neil Immerman explores the computational complexity of planning for distributed agents with partial state information. The authors extend the Markov Decision Process (MDP) and Partially Observable MDP (POMDP) models to allow for decentralized control, introducing the Decentralized Partially Observable MDP (DEC-POMDP) and Decentralized MDP (DEC-MDP) models. They show that solving finite-horizon DEC-POMDP problems with a constant number of agents is complete for nondeterministic exponential time (NEXP), and solving finite-horizon DEC-MDP problems with a constant number of agents is also NEXP-complete. These results highlight a fundamental difference between centralized and decentralized control, suggesting that decentralized planning problems are more computationally challenging than their centralized counterparts. The authors provide a reduction from the TILING problem, a known NEXP-complete problem, to demonstrate the hardness of their models. The findings have implications for the design of algorithms and suggest that different approaches may be necessary for solving decentralized planning problems compared to centralized ones.The paper "The Complexity of Decentralized Control of Markov Decision Processes" by Daniel S. Bernstein, Shlomo Zilberstein, and Neil Immerman explores the computational complexity of planning for distributed agents with partial state information. The authors extend the Markov Decision Process (MDP) and Partially Observable MDP (POMDP) models to allow for decentralized control, introducing the Decentralized Partially Observable MDP (DEC-POMDP) and Decentralized MDP (DEC-MDP) models. They show that solving finite-horizon DEC-POMDP problems with a constant number of agents is complete for nondeterministic exponential time (NEXP), and solving finite-horizon DEC-MDP problems with a constant number of agents is also NEXP-complete. These results highlight a fundamental difference between centralized and decentralized control, suggesting that decentralized planning problems are more computationally challenging than their centralized counterparts. The authors provide a reduction from the TILING problem, a known NEXP-complete problem, to demonstrate the hardness of their models. The findings have implications for the design of algorithms and suggest that different approaches may be necessary for solving decentralized planning problems compared to centralized ones.