Can we efficiently convert from NFA to smallest equivalent DFA?
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.