I ran into a question on previous Mid-Exam. anyone could clarify me?
Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight.
Problem B: Given a Complete Weighted Graph G and Real Number R, Is G has a Hamiltonian Tour with weight at most R?
Suppose there is a machine that solves B. with how many times call of B (each time G and Real number R are given), We Can solve problem A with that machine? suppose the sum of Edges in G up to M.
1) We cannot do this, because there is uncountable state. 2) O(|E|) times 3) O(lg m) times 4) because A is NP-Hard, This is cannot be done.