An algorithm that minimises the number of states for a conversion from a DFA to an NFA I am looking for an algorithm that can convert from a DFA to an NFA, while at the same time producing the minimum number of states for the NFA.  My gut tells me this can be done with around $n$ states, where the DFA has $O(2^n)$ states.  That is, I do not care how many transitions there are, only about the number of NFA states. I am not a graph-theorist, but it seems to me that there should be an algorithm based on the relationship between the number of vertices(states) and edges(transitions) based on Euler's equation.
Said in another way, I am not attempting to minimize the NFA, but to use a minimized DFA to construct an NFA that has fewer states than the DFA.
Pseudo-code is most welcome.
 A: By definition, DFA is itself an NFA. So, conversion from DFA to NFA doesn't make much sense. But, you can always convert a DFA to an equivalent DFA with minimum number of states. There are several algorithms for that purpose. The best known time complexity is $O(n\log\log n)$, where $n$ is the number of states in the DFA.
A: There are arbitrarily large DFAs where the minimum number of states is not reduced at all by access to the epsilon relation.  An example is a DFA on a alphabet of $\Sigma$ with 2k symbols, $a_1, a_2 \cdots a_k$ and $b_1, b_2, \cdots b_k$ and which only accepts strings of the form $a_i b_i$ and nothing else. Then the minimal DFA has k+2 states and the minimal NFA has k+1 states. So one cannot in general go from around $2^n$ states to around $n$ states. 
Now to give an answer to your primary question: I'm not aware of a general solution which isn't essentially brute force. There's a decently efficient algorithm for deciding whether two DFAs describe the same language. See https://arxiv.org/abs/0907.5058 . So, one thing one could do is a brute force search of all NFAs on the alphabet in question. For each, convert the NFA into a DFA and test if it matches your DFA. Do this on all NFAs of size n, iterating n until you find a match (which is then minimal). Unfortunately, the number of NFAs with n states grows roughly exponentially in $n$, so this isn't going to be very efficient. The good news is that the algorithm given above for determining if  two DFAs match is pretty efficient.  My guess though is that there isn't going to be any highly efficient method for finding the smallest NFA which matches a given DFA, and also that proving this would be very difficult. 
