Hamiltonian Weighted Graph and Decision Problems

Question

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.

Answer 1

This is not an answer, I just needed more space than in the comment to follow my discussion with Xoff

I'm just showing here that if you know the minimal weight $R_m$ of an Hamiltonian cycle, you can effectively build one of weight $R_m$ using $|E|$ calls to B.

I assume here that all the weight are positive.

I denote here $B(G,w,R)$ the call of $B$ on $G$ with weight function $w$ and bound $R$.

Let $\{e_1,...,e_n\}$ be the edges of the graph $G$.

Consider the weight function $w_1$ such that $w_1(e_1)=w(e_1)+R_m$ and $w_1(e_i)=w(e_i)$ for $i\neq 1$.

If $B(G,w_1,R_m)$ is false we mark $e_1$.

More generally we define $w_k$ as $w_k(e_k)=w_{k-1}(e_k)+R_m$ and $w_k(e_i)=w(e_i)$ if $e_i$ is marked and for $w_k(e_i)=w_{k-1}(e_i)$ otherwise.

Again if $B(G,w_k,R_m)$ is false we mark $e_k$.

At the end all the edges marked belong to a cycle of weight $R_m$.

Answer 2

Real numbers can not be manipulated by machines : they have infinite size and you can't even answer such a simple question as $$x=y$$ on real numbers in finite time.

Having a machine $B$ that deals with infinite input is quite strange (It output a single bit however). How do you give the input to $B$ ? How do you manipulate the input ?

I think the question is not ok due to this problem. So I would answer 1 : We cannot do this, because there is uncountable state. But it's not really satisfying, it really depends of what's thoughts were in the teacher mind when he wrote the question.

Any reals manipulation in computability must be well defined (are they floating numbers, are they computable reals defined by an algorithm, are they infinite list of digits or are they defined by infinite closed intervals like continued fractions). Depending of definitions, you can or can't do some basic things like compare or add numbers. Without proper definition, we can only assume the worst, and we can't manipulate them.