Classes de complexidade potencialmente iguais sem relativizações contraditórias conhecidas

Quais são alguns exemplos de pares de classes de complexidade e que $A$ $B$

não sabemos se e $A=B$
também não conhecemos relativizações contraditórias (isto é, não conhecemos oráculos e tal forma que e )? $P$ $Q$ $A^P = B^P$ $A^Q \ne B^Q$

Para formular a pergunta de outra maneira, quais são algumas exceções à heurística que, se não é possível descobrir relativizações contraditórias, é fácil resolver a questão da igualdade de maneira definitiva?

cc.complexity-theory complexity-classes relativization Timothy Chow
fonte

Alguma duas classes A e B, para as quais não sabemos como provar uma separação oráculo entre A e B, seria suficiente para responder à sua pergunta? (Assumindo que é possível para A e B para ser igual.)

Robin Kothari

Você aceitaria exemplos sobre implicações entre igualdade, em vez de igualdade única? Por exemplo, não sabemos se NP = UP implica que o PH entra em colapso, mas também não temos um oráculo em que essa implicação seja falsa.

Joshua Grochow 11/11/2015

@ JoshuaGrochow: Isso é interessante, embora eu esteja um pouco mais interessado no tipo específico de exemplo que descrevi.

Timothy Chow

@Robin Kothari: Se não conhecemos um oráculo Q, então, fortiori, não conhecemos os oráculos P e Q, então a única maneira que eu vejo (A, B) para satisfazer suas necessidades, mas a minha não é se sabemos que A = B, mas não conhecemos um oráculo que os separa. Eu acho que pode ser interessante ver um exemplo de A e B de modo que A = B ainda seja plausível (mas não conhecido) que eles possam ser separados por um oráculo, mas isso não é realmente o que eu estava pedindo.

Timothy Chow

Respostas:

Eu acho que o maior exemplo atualmente é (tempo polibomial quântico) vs (hierarquia polinomial do tempo). Foi feito um esforço significativo para separá-los em relação a um oráculo, sem sucesso. (É claro que um oráculo poderoso o suficiente irá torná-los iguais.) E o melhor resultado de contenção sabe é que está em . $BQP$ $PH$ $BQP$ $PP$

Algumas referências para ataques ao problema do oracle: http://arxiv.org/abs/0910.4698 http://arxiv.org/abs/1007.0305

Ryan Williams
fonte

Na realidade, o melhor resultado conhecido é

, onde

é (entre outras coisas) o maior sublcass lacuna-definível de

tal que

. Não tenho conhecimento de nenhum interesse na classe

além de sua relação com

e com

B Q P \subseteq A W P P \subseteq P P

$\mathsf{BQP \subseteq AWPP \subseteq PP}$

A W P P

$\mathsf{AWPP}$

P P

$\mathsf{PP}$

P P^{A W P P} = P P

$\mathsf{PP^{AWPP} = PP}$

A W P P

$\mathsf{AWPP}$

B Q P

$\mathsf{BQP}$

P P

$\mathsf{PP}$ , portanto, como um refinamento, isso é um pouco técnico, mas lá está.

Niel de Beaudrap

Nesse sentido, também não se sabe como separar BQP de AM ou mesmo QMA de AM.

226156 RobinBottai

Existe um oráculo conhecido por separar de ? $\mathsf{P}^{\#\mathsf{P}}$ $\mathsf{PSPACE}$

Ryan O'Donnell
fonte

Tenho certeza de que a questão foi destinado mais retoricamente, isto é, "Eu acho que isso é uma resposta, mas talvez haja um oráculo conhecido que eu não estou ciente de"

Joshua Grochow

Sim, obrigado Josh. Você conhece um? É muito difícil procurar, mas lembro-me de não ter aprendido a existência da última vez que tentei.

Ryan O'Donnell