Can we efficiently convert from NFA to smallest equivalent DFA? Definitions
For any automaton $X$, let $L(X)$ denote the language recognized by $X$.
For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$.

Conversion Problem: NFA to smallest equivalent DFA
Input: A nondeterministic finite automaton $A$.
Output: A smallest possible deterministic finite automaton $B$ such that $L(A) = L(B)$.

We can solve this problem by converting from NFA to DFA using the powerset construction and then minimizing the resulting DFA.  However, this seems inefficient.
In particular, it seems that this could run for $O(2^{sc(L)})$ time where $L = L(A)$ if the powerset construction gives us a suboptimal DFA.

Question: Is there an algorithm for this problem that runs in linear time in terms of the state complexity?  By this, I mean that it runs in $O(n + sc(L))$ time where $n$ is the size of $A$ and $L = L(A)$?  What about $poly(n + sc(L))$ time?
See here:
https://cs.stackexchange.com/questions/61113/does-a-given-e-nfa-accepts-all-the-strings
&quot;checking whether an NFA accepts all strings is PSPACE-complete&quot;.
In particular, if an NFA accepts all strings then its smallest equivalent DFA has size 1, and so a positive answer to your question would imply P=PSPACE.