¿Existe una referencia definitiva para las máquinas de Turing con múltiples cintas oracle?

10

La mayor parte de la literatura parece estar relacionada con máquinas con oráculos individuales para problemas específicos, sin embargo, parece haber algunos documentos que consideran máquinas con oráculos múltiples. ¿Existe un buen trabajo o tesis que proporcione una visión general de lo que se sabe sobre tales máquinas? En particular, estoy interesado en P con múltiples oráculos.

oracles turing-machines Joe Fitzsimons
fuente
3
Si solo desea un número finito N de oráculos, puede definir un oráculo compuesto N-en-1 utilizando los primeros bits de registro (N) del oráculo compuesto para indicar qué suboracle desea consultar. ¿Me estoy perdiendo de algo?
Niel de Beaudrap
Sí, había pensado en eso. Sin embargo, estoy interesado en conjuntos específicos de oráculos, por lo que parece más natural considerarlos por separado que como un objeto compuesto. Pensé que tal vez podría haber algunos buenos resultados en esta dirección.
Joe Fitzsimons
1
solo por curiosidad, ¿tener múltiples oráculos agrega más potencia computacional con respecto a una sola máquina oráculo? Me parece que no, porque simplemente tomas el oráculo correspondiente al idioma en la clase de mayor complejidad. Además, tener un número fijo de oráculos disminuirá la velocidad de la máquina de forma constante.
Marcos Villagra
1
Estoy con el comentario de Marcos sobre el oráculo más fuerte que subsume a los demás ... ¡pero estoy interesado en lo que tenías en mente ahora!
Daniel Apon
1
¿Está pensando en permitir infinitos oráculos, donde el TM puede elegir qué oráculo consultar? Con tal configuración, podría haber una diferencia interesante entre un conjunto de oráculos en el que cada uno era estrictamente más débil que algún otro oráculo Q, y Q en sí.
András Salamon

Respuestas:

5

Aquí hay un artículo más reciente que da una diferencia entre los oráculos simples y múltiples motivados por la criptografía:

Donald Beaver y Joan Feigenbaum. Ocultando instancias en consultas multioracle . STACS 1990. Springer Lecture Notes in Computer Science, 1990, Volumen 415/1990, 37-48, DOI: 10.1007 / 3-540-52282-4_30

Joshua Grochow
fuente
solo una pregunta, supongo que el concepto de oráculo múltiple solo tiene sentido si los oráculos no pueden colapsarse entre sí por alguna (¿percibida?) razones de seguridad?
Ahmed Masud
3

Aquí hay un documento anterior que puede resultarle útil: Máquinas de espacio de registro con múltiples cintas de Oracle por Nancy Lynch en MIT ( PDF ) En particular, el Teorema 2.2, en PDF-página 5, podría ser el tipo de cosa que estás buscando. También hay una sección sobre jerarquías definidas por diferentes números de cintas oráculo por máquina.

Descargo de responsabilidad después del hecho: Parece que se dio una pregunta similar y una respuesta (aún más similar) aquí .

Daniel Apon
fuente