2
$\begingroup$

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.

  • 0
    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?2012-12-10

1 Answers 1

1

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!