Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion?
It is well known that NFA universality (given an NFA, does it accept all words?) is PSPACE-complete. This easily implies that the following problem is PSPACE-complete:


  Given an NFA, is there an equivalent DFA with exactly one state?


To show that the problem is in PSPACE, note that in order to show that an NFA isn't equivalent to a DFA with exactly one space, it suffices to show that its language is not universal (known to be in PSPACE) and non-empty (can be checked in P).

To show that the problem is PSPACE-hard, we reduce from NFA universality. Given an NFA $A$ over the alphabet $\Sigma = \{0,1\}$, we construct an NFA for the language $L = \epsilon + 0\Sigma^* + 1L(A)$; this requires adding a constant number of states. The language $L$ is never empty, and it is universal iff $L(A)$ is, hence $L(A)$ is universal iff $L$ is accepted by a DFA having a single state.