RP (complejidad)

En la teoría de la complejidad computacional, el tiempo polinómico aleatorio (RP) es la clase de problemas de complejidad para los que existe una máquina de Turing probabilística con estas propiedades:

• Siempre funciona en el tiempo polinomio en el tamaño de la entrada
• Si la respuesta correcta es NO, siempre vuelve NO
• Si la respuesta correcta es SÍ, entonces vuelve SÍ con probabilidad al menos 1/2 (otros, regresa NO).

En otras palabras, el algoritmo puede lanzar una moneda verdaderamente aleatoria mientras se está ejecutando. El único caso en el que el algoritmo puede devolver SÍ es si la respuesta real es SÍ; por lo tanto, si el algoritmo termina y produce SÍ, entonces la respuesta correcta es definitivamente SÍ; sin embargo, el algoritmo puede terminar con NO independientemente de la respuesta real. Es decir, si el algoritmo devuelve NO, podría estar equivocado.

Algunos autores llaman a esta clase R, aunque este nombre se usa más comúnmente para la clase de lenguajes recursivos.

Si la respuesta correcta es SÍ y el algoritmo se ejecuta n veces con el resultado de cada ejecución estadísticamente independiente de los demás, devolverá SÍ al menos una vez con probabilidad al menos 1 − 2⁻ⁿ. Entonces, si el algoritmo se ejecuta 100 veces, entonces la posibilidad de que dé la respuesta incorrecta cada vez es menor que la posibilidad de que los rayos cósmicos corrompan la memoria de la computadora que ejecuta el algoritmo. En este sentido, si se dispone de una fuente de números aleatorios, la mayoría de los algoritmos en RP son muy prácticos.

La fracción 1/2 en la definición es arbitraria. El conjunto RP contendrá exactamente los mismos problemas, incluso si el 1/2 se reemplaza por cualquier probabilidad constante distinta de cero menor que 1; aquí constante significa independiente de la entrada al algoritmo.

Definición formal

Un lenguaje L está en RP si y solo si existe una máquina de Turing probabilística M, tal que

• M se ejecuta para el tiempo polinomio en todas las entradas
• Para todos x dentro L, M productos 1 con probabilidad superior o igual a 1/2
• Para todos x no en L, M productos 0

Alternativamente, RP se puede definir usando solo máquinas de Turing deterministas. Un lenguaje L está en RP si y solo si existe un polinomio p y una máquina de Turing determinista M, tales eso

• M se ejecuta para el tiempo polinomio en todas las entradas
• Para todos x dentro L, la fracción de cuerdas Sí. de longitud p(en inglés)xi) Que satisfacen M()x,Sí.)=1{displaystyle M(x,y)=1} es mayor o igual a 1/2
• Para todos x no en L, y todas las cuerdas Sí. de longitud p(en inglés)xTEN), M()x,Sí.)=0{displaystyle M(x,y)=0}

En esta definición, la cadena y corresponde a la salida de los lanzamientos aleatorios de monedas que habría hecho la máquina de Turing probabilística. Para algunas aplicaciones, esta definición es preferible ya que no menciona las máquinas de Turing probabilísticas.

Clases de complejidad relacionadas

RP en relación con otras clases de complejidad probabilística (ZPP, co-RP, BPP, BQP, PP), que generalizan P dentro de PSPACE. Se desconoce si alguna de estas contracciones es estricta.

La definición de RP dice que una respuesta SÍ siempre es correcta y que una respuesta NO puede ser incorrecta, ya que una instancia SÍ puede devolver una respuesta NO. La clase de complejidad co-RP es el complemento, donde una respuesta SÍ puede ser incorrecta mientras que una respuesta NO siempre es correcta.

La clase BPP describe algoritmos que pueden dar respuestas incorrectas tanto en SÍ como en NO, y por lo tanto contiene tanto RP como co-RP. La intersección de los conjuntos RP y co-RP se denomina ZPP. Así como RP puede llamarse R, algunos autores usan el nombre co-R en lugar de co-RP.

Conexión a P y NP

P es un subconjunto de RP, que es un subconjunto de NP. De manera similar, P es un subconjunto de co-RP que es un subconjunto de co-NP. No se sabe si estas inclusiones son estrictas. Sin embargo, si la conjetura comúnmente aceptada P = BPP es cierta, entonces RP, co-RP y P colapso (son todos iguales). Suponiendo además que P ≠ NP, esto implica que RP está estrictamente contenido en NP. No se sabe si RP = co-RP, o si RP es un subconjunto de la intersección de NP y co-NP, aunque esto estaría implicado por P = BPP.

Un ejemplo natural de un problema en co-RP que actualmente no se sabe que esté en P es la prueba de identidad polinomial, el problema de decidir si una expresión aritmética multivariante dada sobre los enteros es el polinomio cero. Por ejemplo, x·x − y·y − (x + y)·(x − y) es el polinomio cero mientras que x·x + y·y no lo es.

Una caracterización alternativa de RP que a veces es más fácil de usar es el conjunto de problemas reconocibles por máquinas de Turing no deterministas donde la máquina acepta si y solo si al menos una fracción constante de las rutas de cálculo, independientes del tamaño de entrada, aceptar. NP por otro lado, solo necesita una ruta de aceptación, que podría constituir una fracción exponencialmente pequeña de las rutas. Esta caracterización hace evidente el hecho de que RP es un subconjunto de NP.