title: Proof the longest path is NP-Hard with negative edge weights
body: <p>I know a similar question has been asked before and that there are abundant amount of resources online, but I have a slightly different question. I understand the reduction from HAM Path to Longest Path. It relies on both needing to use n-1 edges. But what if the graph given in the longest path had a negative edge weight. Then the longest path could have n-2 edges, but HAM would still have n-1 edges. </p>
  
  <p>Is there a different kind of reduction for this problem? Am I missing something?</p>