Mecanismo de acesso ao Oracle Ruzzo-Simon-Tompa

11

Em um artigo sobre a relativização dos cálculos do espaço de log, Ladner e Lynch constroem um oráculo em relação ao qual . Existem alguns exemplos mais patológicos nessa veia na literatura. Eu tenho lido alguns artigos sobre classes espaciais pequenas relativizadas, e uma das principais ferramentas nesta área é o mecanismo de acesso ao oráculo Ruzzo-Simon-Tompa (RST), que exige que uma máquina de turing não-determinística, limitada no espaço, aja de maneira determinística ao fazer consultas ao oráculo.NLP

Agora considere famílias circuito com portões oracle - digamos, AB , onde A é uma classe de complexidade de circuito contendo logspace com acesso oráculo para outra classe B , através de portões oracle acrescentados à base de A . Existem exemplos patológicos semelhantes em espírito ao artigo de Ladner-Lynch, conhecido por essas classes? O que seria uma restrição semelhante ao RST necessária para essas classes? No caso de tais exemplos, estou certo ao supor que um análogo do RST seria insistir em que A seja uma família de circuitos uniforme para o espaço de log?

Nikhil
fonte

Respostas:

8

Uma definição de acesso oracle que funciona para classes de complexidade de circuitos pequenos (as hierarquias ACk e NCk ), bem como para classes de espaço logarítmico, com a propriedade que todas as inclusões conhecidas se relativizam, pode ser encontrada neste documento:

Klaus Aehlig, Stephen Cook e Phuong Nguyen: relativizando pequenas classes de complexidade e suas teorias, CSL 2007, Springer LNCS 4646

Jan Johannsen
fonte
1
Obrigado pelo ponteiro. Mas ainda não tenho uma idéia clara de como o RST se aplica a circuitos com portões da Oracle. Espero que você não se importe se eu esperar um pouco para ver se há outras opiniões interessantes sobre esse assunto, antes de aceitar sua resposta.
Nikhil