title: Complete Weighted Graph and Hamiltonian Tour
body: <p>I ran into a question on a midterm exam. Can anyone clarify the answer?</p>
  
  <p>Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight.</p>
  
  <p>Problem B: Given a Complete Weighted Graph G and Real Number R, does G have a Hamiltonian Tour with weight at most R?</p>
  
  <p>Suppose there is a machine that solves B. How many times can we call B (each time G and Real number R are given),to solve problem A with that machine? Suppose the sum of Edges in G up to M.</p>
  
  <p>1) We cannot do this, because there is uncountable state.</p>
  
  <p>2) O(|E|) times</p>
  
  <p>3) O(lg m) times</p>
  
  <p>4) because A is NP-Hard, This is cannot be done.</p>