The time complexity of supervisory control design for a general class of pr
oblems is studied, It is shown to be very unlikely that a polynomial-time a
lgorithm can be found when either 1) the plant is composed of m components
running concurrently or 2) the set of legal behaviors is given by the inter
section of n legal specifications. That is to say, in general, there is no
way to avoid constructing a state space which has size exponential in m + n
, It is suggested that, rather than discouraging future work in the field,
this result should point researchers to more fruitful directions, namely, s
tudying special cases of the problem, where certain structural properties p
ossessed by the plant or specification lend themselves to more efficient al
gorithms for designing supervisory controls. As no background on the subjec
t of computational complexity is assumed, we have tried to explain all the
borrowed material in basic terms, so that this paper may serve as a tutoria
l for a system engineer not familiar with the subject.