Resultados do Oracle em P vs BPP

10

Seja qualquer problema completo de EXP. Em seguida, . $A$ $P^A = NP^A$

Deixe ser algum oráculo que leva em contas as consultas que (a TM em P) vai fazer, e podemos obter . $B$ $M$ $P^B \neq NP^B$

Pergunta: Temos resultados semelhantes de oracle para P vs BPP?

cc.complexity-theory oracles relativization Kaveh
fonte

2

Sim, mas não tenho certeza de encontrar uma citação. (Bem, a primeira parte é fácil, dar ambas as classes um oráculo para um problema EXP-completo.)

Robin Kothari

3

Se você acha de configuração PCP como verificador ter acesso oráculo para prover (onde a consulta oracle

retornaria o

pouco da prova), então sabemos que, se você permitir verificador para ser uma máquina BPP com

aleatoriedade e

consultas em seguida, a classe de idiomas é calculado

e quando o verificador é uma máquina P (que é não aleatoriedade) com

(mesmo com

) consulta, em seguida, a classe de idiomas é calculado

. Esta não mostra uma separação, a menos que a Oracle

. Mas apenas um exemplo em que o acesso da Oracle a

i

$i$

i^{t h}

$i^{th}$

\log n

$\log n$

3

$3$

N P

$NP$

3

$3$

\log n

$\log n$

P

$\bf P$

P \neq N P

$\bf P \neq \bf NP$

"parece" mais poderoso.

B P P

$\bf BPP$

Sajin Koroth

@RobinKothari Let

então, se

é qualquer problema completo

, não temos

(última desigualdade por hierarquia de tempo)? Então

\oplus P = N P = E X P

$\oplus P=NP=EXP$

A

$A$

E X P

$EXP$

N P^{A} = N P^{\oplus P} = \oplus P^{\oplus P} = \oplus P = N P = E X P \neq P

$NP^A=NP^{\oplus P}=\oplus P^{\oplus P}=\oplus P=NP=EXP\neq P$

enquanto

é mostrado?

P^{A} = N P^{A} ⟹ P^{\oplus P} = N P = \oplus P

$P^A=NP^A\implies P^{\oplus P}=NP=\oplus P$

P \neq N P

$P\neq NP$

T ....

13

Eu tinha uma vaga lembrança de que conhecia uma excelente referência para essas separações de oráculos. Eu finalmente encontrei.

Uma excelente referência para separações de oráculos (para classes entre P e PSPACE) é o seguinte artigo :

Vereshchagin, NK (1994), "Teoremas RELATIVIZÁVEIS E NÃO RELATIVIZÁVEIS NA TEORIA POLINOMIAL DE ALGORITMOS", Academia Russa de Ciências. Izvestiya Mathematics 42 (2): 261

O artigo mostra (ou cita) uma separação oráculo entre quase todos os pares de classes com os quais você pode se interessar entre P e PSPACE (por exemplo, possui classes como P, RP, BPP, UP, FewP, NP, MA, AM , outros níveis de PH, PH, IP, PSPACE etc.).

Por exemplo, o Teorema 8 mostra um problema do oracle no coRP que não está no NP. Como o coRP (relativo a todos os oráculos) está no BPP e o NP contém P, obtemos um problema do oracle no BPP que não está no P.

Como mencionei no meu comentário, mostrar um oráculo para o qual é fácil. Seja A um idioma completo para EXP ou um idioma completo para PSPACE. $\text{P}^A = \text{BPP}^A$

Robin Kothari
fonte

aqui está o link Download de citeseer citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1232

Marcos Villagra

Embora se você puder obter a versão completa, eu recomendaria isso. A versão citeseer não possui números e, portanto, está faltando um bom diagrama de inclusão de classes de complexidade (Fig 1).

Robin Kothari

8

O zoológico de complexidade é seu amigo! Como Robin disse, você tem metade da resposta: qualquer problema de EXP-completo reduz NP a P e, portanto, BPP a P. Buhrman e Fortnow construíram um oráculo em relação ao qual P = RP, mas BPP não é igual a P. Isso é mais do que o que você pediu; Eu suspeito que existem construções mais fáceis que separam P do RP e do BPP.

Sasho Nikolov
fonte

6

Uma boa descrição de um oráculo que separa P e BPP é dada por Greg Kuperberg em um dos comentários deste interessante post do blog , onde Terence Tao descreve máquinas de Turing com oráculos e resultados de complexidade em relação a oráculos na forma de uma alegoria.

Alessandro Cosentino
fonte

11

isso é uma descrição cool :)

Sasho Nikolov

-1

Bennett e Gill dão oráculos para ambos os casos: http://epubs.siam.org/doi/abs/10.1137/0210008

Luke Mathieson
fonte

Eles dão um oráculo para separar BPP de P? Não consegui encontrar essa afirmação no jornal.

22612 Robin Kothari

Eu achava que sim, infelizmente estou longe do meu escritório e não tenho acesso ao pdf. Vou ter que verificar mais tarde.

Luke Mathieson

B P P^{A} = P^{A}

$BPP^{A} = P^{A}$

Resultados do Oracle em P vs BPP

Respostas: