Máquina de Turing Oracle

Question

Estoy aprendiendo complejidad computacional y esta es una pregunta de mi tarea que tengo problemas tratando de resolver/entender.

Una Máquina de Turing de oráculo M con oráculo A es una Máquina de Turing con una cinta de consulta adicional y tres estados especiales, denominados Qquery, Qyes y Qno. Cada vez que M entra en el estado Qquery, en un paso pasa al estado Qyes o Qno, dependiendo de si la cadena de la cinta de consulta está o no en el conjunto A; también vacía la cinta de consulta.

Un conjunto A es autorreducible si existe una máquina oráculo M determinista de tiempo polinómico tal que se cumple lo siguiente:

• A = L(M;A), donde L(M;A) es el lenguaje decidido por la máquina M con un oráculo para el conjunto A, y
• La máquina M -con entradas de longitud n- consulta al oráculo sólo sobre cadenas de longitud n-1 como máximo.

Demostrar que el conjunto que incluye todos los grafos hamiltonianos es autorreducible.

Answer 1

Pista:

No estoy seguro de haber entendido bien la pregunta, pero probablemente quiera hacer algo así:

• Por cada $4$ vértices $a, b, c, d$ formando un camino:

  • eliminar $b$ y $c$ del grafo con todas las aristas adyacentes,
  • añadir nuevo vértice $x$ junto con los bordes $(a,x)$ y $(x,d)$ ,
  • dar nombre al nuevo gráfico $G'$ y ejecutar oracle en él (tiene $n-1$ vértices y como máximo $m-1$ bordes),
  • devolver 'sí' si oráculo dijo 'sí'.
• Devuelve 'no' si el oráculo dijo 'no' cada vez.

Recuerda, esto es sólo una idea, ¡lo que cuenta es la prueba!