  In this paper we examine the difficulty of finding an equivalent
deterministic automaton when confronted with a non-deterministic one. While for
some automata the exponential blow-up in their number of states is unavoidable,
we show that in general, any approximation of state complexity with polynomial
precision remains PSPACE-hard. The same is true when using the subset
construction to determinize the NFA, meaning that it is PSPACE-hard to predict
whether subset construction will produce an exponential ''blow-up'' in the
number of states or not. To give an explanation for its behaviour, we propose
the notion of subset complexity, which serves as an upper bound on the size of
subset construction. Due to it simple and intuitive nature it allows to
identify large classes of automata which can have limited non-determinism and
completely avoid the ''blow-up''. Subset complexity also remains invariant
under NFA reversal and allows to predict how the introduction or removal of
transitions from the NFA will affect its size.
