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

Computational complexity results are obtained for decentralized discrete-event control problems. These results generalize the earlier work of Tsitsiklis, who showed that for a special class of centralized supervisory control problems under partial observation, there is an algorithm for determining in polynomial time whether or not a solution exists. The negative complexity results associated with Tsitsiklis' work also 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 solutions when such solutions exist.