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.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
More Huimen Maisori's questions See All
Similar questions and discussions