$MIN_{NFA}$ is PSPACE complete
For a fixed alphabet, you can describe an NFA with $n$ states using $O(n^2)$ bits. Now, given a DFA $M$ and an integer $n$ (encoded in binary), we consider two cases:


$M$ has at most $n$ states. In this case, there exists an NFA for $L(M)$ having at most $n$ states.
$M$ has more than $n$ states. In this case, the input length is $\Omega(n)$ bits, and so we can guess an NFA with $n$ states in polynomial space.