# Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion?

The canonical NFA to DFA conversion, starting with an NFA with $$n$$ states, can result in a DFA with $$2^n$$ states. However, in many cases, there are states that are "unnecessary," such as when minimizing the resulting DFA. The most common case is when states are "unreachable" from the corresponding start state.

I am interested in the following question: if we have an NFA with $$n$$ states and $$q$$ symbols, is there a $$\mathrm{poly}(n, q)$$-time algorithm to output the number of states that the standard conversion (and minimizing, if possible) to a DFA would produce? Note that producing the DFA itself can take exponential time.

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.