THE COMPUTATIONAL-COMPLEXITY OF DECENTRALIZED DISCRETE-EVENT CONTROL-PROBLEMS

Computational complexity results are obtained for decentralized discre te-event control problems. These results generalize the earlier work o f Tsitsiklis, who showed that for a special class of centralized super visory control problems under partial observation, there is an algorit hm for determining in polynomial time whether or not a solution exists . The negative complexity results associated with Tsitsiklis' work als o carry over to the decentralized case, so that solution existence for the more general class is not decidable in polynomial time, nor does there exist a polynomial-time algorithm for producing supervisor solut ions when such solutions exist.