Existe uma referência definitiva para máquinas de Turing com várias fitas oracle?

A maior parte da literatura parece estar preocupada com máquinas com oráculos únicos para problemas específicos, no entanto, parece haver alguns trabalhos que consideram máquinas com múltiplos oráculos. Existe um bom artigo ou tese que forneça uma visão geral do que se sabe sobre essas máquinas? Em particular, estou interessado em P com múltiplos oráculos.

oracles turing-machines Joe Fitzsimons
fonte

Se você deseja apenas um número finito N de oráculos, você pode definir um oráculo composto N-em-1 usando os primeiros bits de log (N) do oráculo composto para indicar qual suboráculo você deseja consultar. Estou esquecendo de algo?

Niel de Beaudrap

Sim, eu pensei nisso. No entanto, estou interessado em conjuntos específicos de oráculos e, portanto, parece mais natural considerá-los separadamente do que como um objeto composto. Pensei que talvez houvesse bons resultados nessa direção.

Joe Fitzsimons

só por curiosidade, ter múltiplos oráculos acrescenta mais poder computacional em relação a uma única máquina de oráculo? Parece-me que não, porque você apenas pega o oráculo correspondente ao idioma na classe de maior complexidade. Além disso, ter um número fixo de oráculos diminui a velocidade da máquina em uma constante.

Marcos Villagra

Estou com o comentário de Marcos sobre o oráculo mais forte, subsumindo aos outros ... mas estou interessado no que você tinha em mente agora!

Daniel Apon 19/08/10

Você está pensando em permitir infinitamente muitos oráculos, onde a TM pode escolher qual oráculo consultar? Com essa configuração, pode haver uma diferença interessante entre um conjunto de oráculos em que cada um deles é estritamente mais fraco do que algum outro oráculo Q e o próprio Q.

András Salamon

Respostas:

Aqui está um artigo mais recente que mostra a diferença entre oráculos únicos x múltiplos motivados pela criptografia:

Donald Beaver e Joan Feigenbaum. Ocultando instâncias em consultas com vários segmentos . STACS 1990. Springer Lecture Notes in Computer Science, 1990, Volume 415/1990, 37-48, DOI: 10.1007 / 3-540-52282-4_30

Joshua Grochow
fonte

apenas uma pergunta, considero que o conceito de multi-oráculo só faz sentido se os oráculos não puderem ser recolhidos um ao outro por alguns motivos (percebidos?) de segurança?

Ahmed Masud

Aqui está um artigo antigo que você pode achar útil: Logspace Machines with Multiple Oracle Tapes de Nancy Lynch no MIT ( PDF ). Em particular, o Teorema 2.2, na página 5 do PDF, pode ser o tipo de coisa que você está procurando. Há também uma seção sobre hierarquias definidas por diferentes números de fitas Oracle por máquina.

Isenção de responsabilidade após o fato: Parece que uma pergunta semelhante e (ainda mais semelhante) foram dadas aqui .

Daniel Apon
fonte