A Oracles é associativa?

11

Esta pergunta pode ter uma resposta óbvia ... mas aqui está a pergunta de qualquer maneira. Intuitivamente, é a seguinte declaração plausível - "uma máquina com uma sub-rotina A que, por sua vez, possui uma sub-rotina B é a mesma que uma máquina com uma sub-rotina A que tem acesso à sub-rotina B".

Para definir esse problema formalmente, usarei uma notação não convencional. Quando eu digo , eu estou dando um oráculo para um B - C o m p l e t e problema. por exemplo, N P N P = N P S A T = Σ 2 . Com essa notação "nova", é possível definir A B C e assim por diante. Minha pergunta é, éABABCompleteNPNP=NPSAT=Σ2ABC

  • Essa é uma maneira válida de pensar sobre oráculos?
  • é (AB)C=A(BC)

Por exemplo, (NPNP)NP=Σ2NP=NPΣ2=NP(NPNP)

Não consigo pensar em nenhum contra-exemplo óbvio a essa regra. Qualquer um?

gabgoh
fonte
Você já viu minha pergunta: cstheory.stackexchange.com/q/972/873 ?
MS Dousti 26/10/10
11
esta é uma pergunta um pouco mais geral, mas a pergunta de Sadeq é bastante relevante, e especialmente os comentários sobre o-ness mal-formado de A ^ B ^ C se A ^ B não é um modelo computacional
Suresh Venkat
não, mas era exatamente isso que eu batia com a cabeça na parede ontem à noite sobre o que motivou essa pergunta!
gabgoh
Veja também esta pergunta .
Kaveh

Respostas:

5

Como Venkat disse nos comentários, parece difícil entender sua definição para oracle que não é definida como uma caracterização de máquina.

Seja o conjunto de TM em A com um oráculo que é uma máquina em ( B com um oráculo em uma máquina em C ). É óbvio que uma máquina em A pode chamar C : ele só chama a máquina em B e pede-lhe para levar a mensagem diretamente para C .A(BC)ABCACBC

Eu acho que seria uma máquina em A que pode chamar um oráculo em C ou um oráculo que é (uma máquina em B que pode chamar uma máquina em C ), portanto é exatamente a mesma definição.(AB)CACBC

Finalmente, você pode querer , que certamente é diferente dos outros dois (basta pegar B = C = N P e A = P , então A B , C = N P c o N P enquanto A ( B C ) = Σ P 2¸ p 2 .AB,CB=C=NPA=PAB,C=NPcoNPA(BC)=Σ2PΠ2p

Arthur MILCHIOR
fonte
4
Cuidado: P ^ NP inclui NP∪coNP, mas não se sabe ou acredita-se que seja igual a NP∪coNP. Da mesma forma, P ^ (NP ^ NP) não é conhecido por ser igual a ∪Π2P∪Π2P.
Tsuyoshi Ito
11
@ Tsuyoshi, obrigado pela observação, não sei por que pensei nisso. Na verdade, se é evidente que P N P . DeixeiNPcoNPPNP e B ser problemas NPcomplte e coNPcomplete, em seguida, o problema que tomar entrada ( x , y ) e responder verdadeiro se x A e y B é em P N P mas não em N P C O N P . AB(x,y)xAyBPNPNPcoNP
Arthur MILCHIOR
3

Eu escreveria o seguinte como um comentário, mas era muito longo para caber.

Vamos primeiro descrever o significado de "algoritmos na classe com um oráculo para uma linguagem A." (A necessidade disso foi apontada por Tsuyoshi Ito). Usaremos a mesma convenção usada por Ladner e Lynch . A convenção é bem descrita por Bennett & Gill :C

pode ser definido de várias maneiras, dependendo da forma como a fita de consulta é tratado. Seguimos as convenções de Ladner e Lynch [LL]: A fita de consulta não é cobrada no espaço vinculado, mas para evitar que seja usada como fita de trabalho, a fita de consulta é unidirecional e somente para gravação e é apagada seguindo automaticamente cada consulta. (Simon [Si] trata a fita de consulta como uma das fitas de trabalho, uma fita de leitura / gravação bidirecional que é carregada no espaço limitado. A definição de Ladner-Lynch é menos restritiva e talvez mais natural, já que para um oráculo aleatórioA L O G S P A C E ALOGSPACEAALOGSPACEA vale com probabilidade 1 para [LL] mas não para [Si])

[LL] RE LADNER E NA LYNCH, Relativização de perguntas sobre computabilidade do espaço de log , Matemática. Systems Theory, 10 (1976), pp. 19-32.

[SIM] J. SIMON, sobre alguns problemas centrais na complexidade computacional , Tech. Representante TR 75-224, Departamento de Ciência da Computação, Cornell University, Ithaca, NY, 1975.

A definição padrão de classes de complexidade de máquinas Oracle é a seguinte: Seja B e C sejam classes de complexidade . Então, é uma classe de complexidade legítimo, definida como X = L C B G . Aqui, B L representa a classe complexidade dos problemas de decisão solucionável por um algoritmo na classe B com um oráculo para uma linguagem L.X=BCX=LCBLBL

Desde X é uma classe de complexidade legítimo, para qualquer classe de complexidade A, podemos falar de classes de complexidade e X A = ( B C ) A .AX=A(BC)XA=(BC)A

  • refere-se à classe de complexidade de problemas de decisão que podem ser resolvidos por um algoritmo de classe A, com um Oracle para qualquer língua L 'X = L C B G . Em outras palavras, A XAXLX=LCBL .AX=L{LCBL}AL

  • refere-se à classe de complexidade de problemas de decisão que podem ser resolvidos por um algoritmo de classe X = L C B G com um Oracle para qualquer língua L 'Uma . Em outras palavras, X A = L A X L = XAX=LCBLLA .XA=LAXL=LA(LCBL)L

Reivindicação: .(BL1)L(BL2)L=(BL)L1L2

Side Note: Since it's 3:00 AM now, I'm too sleepy to check the validity of the above claim! I think it's valid & elementary to prove, yet it's nice to see the actual proof.

Portanto, pode-se escrever .XA=LA(LCBL)L=LC,LA(BL)L

Exemplo

Deixe . Sabemos que c O N PX . Dando aos dois lados acesso do oráculo a N P , obtém-se:X=PNPcoNPXNP .coNPNPXNP=(PNP)NP

Epílogo

Uma discussão frutuosa com Tsuyoshi Ito revelou (para mim) que não é fácil relativizar duplamente uma aula de complexidade. De fato, mesmo definir um deles parece ser problemático. Eu definitivamente deveria estudar mais para ver se alguma definição satisfatória é dada. Enquanto isso, aprecio qualquer comentário que possa ser usado para resolver esse problema.

MS Dousti
fonte
4
Como comentei em outra pergunta , “o algoritmo da classe B com um oráculo para uma linguagem L” não tem uma definição universalmente aceita em geral.
Tsuyoshi Ito
@ Tsuyoshi: editei a resposta para representar qual definição estou usando. Remove o mal-formado-ness?
MS Dousti 27/10/10
Não. A parte adicionada apenas define o que LOGSPACE ^ A significa, não o que B ^ A significa para algo como B = NP ^ NP.
Tsuyoshi Ito
@ Tsuyoshi: Obrigado. Acabei de adicionar um exemplo para esclarecer o que quero dizer. Eu quero uma definição tal que se , então AAXACXC
4
Infelizmente, sua “exigência natural” não é de fato tão natural. Embora PSPACE⊆IP e exista uma definição natural e amplamente aceita de IP ^ A para qualquer idioma A (o verificador recebe um acesso Oracle a A), sabe-se que PSPACE ^ A⊈IP ^ A com probabilidade 1 aleatória oráculo A; Vejo Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan e Rohatgi 1994 . Como eu disse, não existe uma definição amplamente aceita de C ^ A para uma classe de complexidade arbitrária C, até onde eu saiba. (mais)
Tsuyoshi Ito