# Oracle turing machine

I am learning computational complexity and this is a question of my assignment that I have issues trying to solve/understand.

An oracle Turing Machine M with oracle A is a Turing Machine with an additional query tape and three special states, say Qquery, Qyes and Qno. Whenever M enters the state Qquery, in one step it moves into state Qyes or Qno, depending on whether or not the string on the query tape is in the set A; it also empties the query tape.

A set A is self-reducible if there is a deterministic polynomial time oracle machine M such that the following holds:

• A = L(M;A), where L(M;A) is the language decided by machine M with an oracle for the set A, and
• machine M -with inputs of length n- queries the oracle about strings of length at most n-1 only.

Prove that the set including all Hamiltonian graphs is self-reducible.

-
The query tape contains strings; $A$ is a set of strings. A Hamiltonian graph is not a string, so by this definition the set of all Hamiltonian graphs isn't self-reducible. Are you perhaps assuming some encoding of graphs as strings? – joriki Dec 10 '12 at 21:58

Hint:

I am not sure if I understand the question correctly, but probably you want to do something like this:

• For every $4$ vertices $a, b, c, d$ forming a path:

• remove $b$ and $c$ from the graph with all the adjacent edges,
• add new vertex $x$ along with edges $(a,x)$ and $(x,d)$,
• name the new graph $G'$ and run oracle on it (it has $n-1$ vertices and at most $m-1$ edges),
• return 'yes' if oracle said 'yes'.
• Return 'no' if oracle said 'no' every time.

Remember, this is only an idea, it is the proof that counts!

-