Circuitos com oráculos vs. Máquinas de Turing com oráculos

Simplificando: qual é a correspondência entre máquinas de Turing com oráculos e famílias uniformes de circuitos com oráculos? Como são definidas as últimas para obter o mesmo modelo computacional para uma determinada máquina de Turing da Oracle?

Essa pode ser uma pergunta elementar, mas não é óbvio para onde procurar, e eu sou o tipo de pessoa que gosta de garantir que minhas fundações usem argamassa de boa qualidade. Se houver uma referência padrão, aponte-me para ela. (O livro de Papadimitriou, por exemplo, parece não descrever circuitos com oráculos.)

Minha hipótese de trabalho é a seguinte: uma família de circuitos uniforme com acesso a um oráculo (por exemplo, para resolver um problema NP-completo) é definida da seguinte maneira:

Um define uma família infinita de "oracle gates" O _n , um para cada tamanho de circuito n, cada um dos quais calcula uma função f _n : {0,1} ^cn → {0,1} para alguma constante c.
As funções f _n calculadas pelos portões oracle O _n devem ser "uniformes" no seguinte sentido: para qualquer n <N e x ∈ {0,1} ⁿ , exigimos f _n ( x ) = f _N (0 ^{c ( N − n)} x ) --- isto é, os portões do oracle devem usar uma "codificação" consistente e extensível de suas entradas.
Em seguida, define-se uma família de circuitos uniforme, em que os portões do oráculo estão entre as operações permitidas para o circuito, restringindo o circuito ao tamanho da entrada n para usar o portão O _n .

Imagino que algumas das opções acima possam ser arbitrariamente fixadas sem perder nenhuma generalidade. O que me interessa é uma referência para a correspondência, ou pelo menos uma descrição de como modificar a descrição acima para obter a padrão.

cc.complexity-theory turing-machines oracles circuit-families Niel de Beaudrap
fonte

Como sei que você trabalha com informações quânticas, eu recomendaria a pesquisa de John Watrous sobre a complexidade computacional quântica, onde ele também fala sobre oráculos em circuitos quânticos e consulta do oráculo em superposição.

Robin Kothari

O artigo de Watrous também é uma boa referência. Mas o que acabei precisando neste caso foi desabilitar a idéia de que alguém iria querer definir uma família de circuitos relativizados de uma maneira que não correspondesse apenas a testar o mesmo predicado para diferentes comprimentos de cordas finitas, por estar lembrou que a semântica de um oráculo classicamente é indicar participação em algum conjunto. Como se viu, desenhos de portões de circuito com os símbolos "∈A?" neles era tudo que eu precisava.

Niel de Beaudrap 26/08/10

Respostas:

A melhor referência para circuitos relativizados é o artigo de Chris Wilson "Relativized NC" http://www.springerlink.com/content/u727654246wu8662/

A segunda condição que você possui (fechamento para baixo de O_n) não é necessária para obter a equivalência entre P ^ O e circuitos poligonais uniformes com o oráculo O. Além disso, sua terceira condição deve ser descartada, o tamanho do circuito impedirá o acesso para O_m para m maior que o tamanho do circuito.

Lance Fortnow
fonte

Não há comentários explícitos no artigo de Wilson sobre os próprios portões do oráculo; mas, em retrospecto, se você levar o oráculo a sério como representando a associação a um conjunto de strings booleanos, como ocorre com as TMs, minha segunda condição é apenas um não-problema (ou seja, é óbvio). Pela sua observação da supérflua da minha terceira condição, basta ter uma família infinita de portões que decidem ser membros de A para qualquer tamanho de corda finito específico. Isso funciona para mim; Eu gostaria de ter pensado nisso.

Niel de Beaudrap

Comentários para o benefício de espectadores casuais - O artigo de Wilson define a contribuição profunda de uma porta do oráculo em k bits a ser o teto (log k), em aparente analogia ao trabalho anterior de Cook ("Uma taxonomia de problemas com algoritmos paralelos rápidos" , Inform. E Control, 64). Há uma questão técnica de permitir consultas ao oráculo no processo de construção dos próprios circuitos (cada um dos quais também pode usar oráculos): ele comenta que isso não parece importar. No final, porém, ele está insatisfeito com a existência de A, na qual NC_1 ^ A não está contido em NSPACE ^ A (O (n ^ k)), para qualquer constante k.

Niel de Beaudrap