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

Question

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.

Answer 1

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.