¿Qué evidencia específica hay para P = RP?

RP es la clase de problemas que puede resolver una máquina de Turing no determinista que termina en tiempo polinómico, pero también se permite un error unilateral. P es la clase habitual de problemas que puede resolver una máquina de Turing determinista que termina en tiempo polinómico.

P = RP se deriva de una relación en la complejidad del circuito. Impagliazzo y Wigderson demostraron que P = BPP sigue si algún problema que puede decidirse en tiempo exponencial determinista también requiere circuitos de tamaño exponencial (tenga en cuenta que P = BPP implica P = RP). Quizás debido a estos resultados, parece haber una sensación entre algunos teóricos de la complejidad de que las reducciones probabilísticas probablemente pueden ser aleatorizadas.

¿Qué otra evidencia específica hay de que P = RP?

La existencia de problemas en DTIME (2 ^ O (n)) que requieren circuitos de tamaño exponencial para calcular (que es la suposición en IW) parece plausible ya que de lo contrario tendríamos falta de uniformidad dando una aceleración en CADA problema computacional, que va completamente en contra del pensamiento actual que no ve una brecha "demasiado significativa" entre la complejidad uniforme y no uniforme para problemas "normales". Este pensamiento proviene del hecho de que hay muy pocos ejemplos en los que se conoce un algoritmo "no uniforme" que sea significativamente mejor que el uniforme uniforme conocido (de nuevo, excepto para la aleatorización).

Otra pieza de "evidencia" es que, en relación con un oráculo aleatorio , tenemos P = BPP.

Cualquier resultado concreto de desrandomización da evidencia de que P = BPP. Como tal, PRIMES en P (Agrawal-Kayal-Saxena'02) es un buen ejemplo. En general, hay pocos problemas naturales en BPP que no se sabe que están en P (las pruebas de identidad polinómica son una excepción notable).

De espíritu similar al resultado que menciona, Hastad-Impagliazzo-Levin-Luby '99 demostró que la existencia de funciones unidireccionales implica la existencia de generadores pseudoaleatorios. Si bien esto no implica directamente P = BPP basado en la existencia de funciones unidireccionales, sí muestra que los generadores pseudoaleatorios se derivan de supuestos criptográficos mínimos. Esto puede verse como otra pista de que BPP no es más poderoso que P.

$P^X=RP^X$ $X$$ZPP=RP=EXP$$P$

Lo anterior es, por supuesto, hablar de desrandomizar las reducciones aleatorias de Turing de tiempo polinomial, en lugar de las reducciones múltiples de tiempo polinomial habituales. No me sorprendería si el oráculo de Heller se puede adaptar para dar un conjunto X tal que para todo Y, Y es exponencial muchas veces reducible a X si Y es reducible por RP a X, pero sin pasar por la construcción I No podía jurarlo.

$USAT_Q$$Q = \bot$$USAT_{\bot}$

$\phi$$\phi$$\phi$$k$$x$$\phi$$k$$x$$k$$x$$k$

$k$$k$$n$$USAT_{\bot}$$n$

$\epsilon > 0$$n^{1-\epsilon}$