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.

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.