  Synthesis of correct by design systems from specification has recently
attracted much attention. The theoretical results imply that this problem is
highly intractable, e.g., synthesizing a system is 2EXPTIME-complete for an LTL
specification, and EXPTIME-complete for a CTL specification. However, an
argument against it is that the temporal specification is highly compact, and
the complexity reflects the large size of the system constructed. In that
respect, the complexity should, perhaps, be specified relative to the size of
the minimal satisfying system. A careful observation reveals that the size of
the system is presented in such arguments as the size of its state space. This
view is a bit nonstandard, in the sense that the state space can be
exponentially larger than the size of a reasonable implementation such as a
circuit or a program. Although this alternative measure of the size of the
synthesized system is more intuitive (e.g., this is the standard way model
checking problems are measured), research on synthesis has so far stayed with
measuring the system in terms of the explicit state space. This raises the
question of whether or not there always exists a small system. In this paper,
we show that this is the case if, and only if, PSPACE = EXPTIME.
