title: Confusion about NP-hard and NP-Complete in Traveling Salesman problems
body: <p>Traveling Salesman Optimization(TSP-OPT) is a NP-hard problem and Traveling Salesman Search(TSP) is NP-complete. However, TSP-OPT can be reduced to TSP since if TSP can be solved in polynomial time, then so can TSP-OPT(1). I thought for A to be reduced to B, B has to be as hard if not harder than A. As I can see in the below references, TSP-OPT can be reduced to TSP. TSP-OPT is supposed to be harder than TSP. I am confused...</p>
  
  <p>References: (1)Algorithm, Dasgupta, Papadimitriou, Vazirani Exercise 8.1 <a href="http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf" rel="noreferrer">http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf</a> <a href="https://cseweb.ucsd.edu/classes/sp08/cse101/hw/hw6soln.pdf" rel="noreferrer">https://cseweb.ucsd.edu/classes/sp08/cse101/hw/hw6soln.pdf</a></p>
  
  <p><a href="http://cs170.org/assets/disc/dis10-sol.pdf" rel="noreferrer">http://cs170.org/assets/disc/dis10-sol.pdf</a></p>