A summary is given of computational complexity results 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. Moreover, even when it can be shown that supervisor solutions exist for problems in either the special or general class, there is no polynomial-time algorithm for producing such solutions.

Back to Discret Event Systems, Manufacturing Systems, and Communiation Networks Table of Contents