Que evidência específica existe para P = RP?

25

RP é a classe de problemas decididos por uma máquina de Turing não determinística que termina em tempo polinomial, mas que também é permitida erro unilateral. P é a classe usual de problemas decidíveis por uma máquina de Turing determinística que termina em tempo polinomial.

P = RP segue de um relacionamento na complexidade do circuito. Impagliazzo e Wigderson mostraram que P = BPP segue se algum problema que pode ser decidido em tempo exponencial determinístico também requer circuitos de tamanho exponencial (observe que P = BPP implica P = RP). Talvez devido a esses resultados, pareça haver um sentimento entre alguns teóricos da complexidade de que as reduções probabilísticas provavelmente podem ser des aleatórias.

Que outras evidências específicas existem de que P = RP?

András Salamon
fonte
Veja também uma pergunta relacionada cstheory.stackexchange.com/questions/364/…
András Salamon

Respostas:

13

A existência de problemas em DTIME (2 ^ O (n)) que exigem circuitos de tamanho exponencial para calcular (que é a suposição em IW) parece plausível, pois, caso contrário, teríamos uma não uniformidade, acelerando TODOS os problemas computacionais - o que vai completamente contra o pensamento atual que não vê uma lacuna "muito significativa" entre complexidade uniforme e não uniforme para problemas "normais". Esse pensamento vem do fato de que existem muito poucos exemplos em que um algoritmo "não uniforme" é conhecido que é significativamente melhor do que o uniforme conhecido (novamente, exceto para des aleatorização).

Outra parte da "evidência" é que, em relação a um oráculo aleatório , temos P = BPP.

Noam
fonte
Eu pensei que era o trabalho preciso que mencionei na pergunta original. o que estou perdendo?
András Salamon
opa, acho que não li a pergunta até o fim ... A razão pela qual a suposição é plausível é que, caso contrário, teríamos uma não uniformidade, acelerando todos os problemas computacionais - o que vai completamente contra o pensamento atual de que não vê uma lacuna "muito significativa" entre complexidade uniforme e não uniforme para problemas "normais".
Noam
1
editado a resposta agora --- ainda conhecer o sistema ...
Noam
9

Qualquer resultado concreto da des randomização fornece evidências de que P = BPP. Como tal, o PRIMES em P (Agrawal-Kayal-Saxena'02) é um bom exemplo. Geralmente, existem poucos problemas naturais no BPP que não são conhecidos por P (o teste de identidade polinomial é uma exceção notável).

De espírito semelhante ao resultado mencionado, Hastad-Impagliazzo-Levin-Luby '99 mostrou que a existência de funções unidirecionais implica na existência de geradores pseudo-aleatórios. Embora isso não implique diretamente P = BPP com base na existência de funções unidirecionais, mostra que os geradores pseudo-aleatórios seguem a partir de suposições criptográficas mínimas. Isso pode ser visto como outra dica de que o BPP não é mais poderoso que o P.

Moritz
fonte
6

É importante notar que dizer "reduções probabilísticas [provavelmente] podem ser des randomizadas" é muito mais forte que P = RP. De fato, uma formalização da noção de des aleatorizar todas as reduções aleatórias é que relação a cada oráculo X , que sabemos ser falso (por exemplo, Heller. Hierarquias polinomiais relativizadas que estendem dois níveis, Teoria dos Sistemas Matemáticos 17 (2) : 71-84, 1984 dá um oracle, em que Z P P = R P = E X P que não é igual a P pela Tempo Hierarquia Teorema).PX=RPX XZPP=RP=EXPP

O exposto acima, é claro, está falando sobre reduções aleatórias de Turing no tempo polinomial aleatório, em vez das reduções usuais de uma vez em tempo polinomial. Eu não ficaria surpreso se o oráculo de Heller pudesse ser adaptado para dar um conjunto X tal que, para todo Y, Y seja exponencial em tempo - muitos redutíveis a X se Y for YR-redutível a X, mas sem passar pela construção I não podia jurar.

Joshua Grochow
fonte
5

USATQQ=USAT

ϕϕϕkxϕkxkxk

kknUSATn

ϵ>0n1ϵ

András Salamon
fonte
PNPP=NP
@ Colin: Sem comentários. :-)
András Salamon