# 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.

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.