RP (complejidad)

Clase de tiempo polinomial aleatorio de la teoría de la complejidad computacional

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

Algoritmo RP (1 ejecución)
Respuesta producida Respuesta correcta	Sí	No
Sí	≥ 1/2	≤ 1/2
No	0	1
Algoritmo RP ( n ejecuciones)
Respuesta producida Respuesta correcta	Sí	No
Sí	≥ 1 − 2 ^{− n}	≤ 2 ^{− n}
No	0	1
Algoritmo co-RP (1 ejecución)
Respuesta producida Respuesta correcta	Sí	No
Sí	1	0
No	≤ 1/2	≥ 1/2

Siempre se ejecuta en tiempo polinomial en el tamaño de entrada.
Si la respuesta correcta es NO, siempre devuelve NO
Si la respuesta correcta es SÍ, entonces devuelve SÍ con una probabilidad de al menos 1/2 (de lo contrario, devuelve NO).

En otras palabras, el algoritmo puede lanzar una moneda al azar mientras está en funcionamiento. 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 utiliza 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, entonces devolverá SÍ al menos una vez con una probabilidad de al menos $1 - 2 - n$ . Entonces, si el algoritmo se ejecuta 100 veces, entonces la probabilidad de que dé la respuesta incorrecta cada vez es menor que la probabilidad de que los rayos cósmicos corrompieran la memoria de la computadora que ejecuta el algoritmo. ^[1] En este sentido, si hay una fuente de números aleatorios disponible, la mayoría de los algoritmos en RP son altamente prácticos.

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

Definición formal

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

M se ejecuta durante un tiempo polinomial en todas las entradas
Para todo x en L , M da como resultado 1 con probabilidad mayor o igual a 1/2
Para todos los x no en L , M da como resultado 0

Alternativamente, la RP se puede definir utilizando únicamente 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 que

M se ejecuta durante un tiempo polinomial p en todas las entradas
Para todo x en L , la fracción de cadenas y de longitud p (| x |) que satisfacen ⁠ ⁠ $M(x,y)=1$ es mayor o igual a 1/2
Para todo x no en L , y todas las cadenas y de longitud p (| x |), ⁠ ⁠ $M(x,y)=0$

En esta definición, la cadena y corresponde al resultado de los lanzamientos aleatorios de moneda que habría realizado 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

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 instancias SÍ como 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 denominarse R , algunos autores utilizan el nombre co-R en lugar de co-RP .

Conexión a P y NP

Problema sin resolver en informática :

⁠ ⁠

{\mathsf {P}}{\overset {?}{=}}{\mathsf {RP}}

(más problemas sin resolver en informática)

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 de P = BPP es verdadera, entonces RP , co-RP y P colapsan (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 implícito 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 Polinómica , el problema de decidir si una expresión aritmética multivariante dada sobre los números 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 las 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, independientemente del tamaño de entrada, acepta. 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 que el hecho de que RP es un subconjunto de NP sea obvio.

Véase también

Referencias

^ Esta comparación se atribuye a Michael O. Rabin en la pág. 252 de Gasarch, William (2014), "Classifying Problems into Complexity Classes", en Memon, Atif (ed.), Advances in Computers, vol. 95 (PDF) , Academic Press, pp. 239–292.

Enlaces externos

RP en el Zoológico de la Complejidad

[1] Esta comparación se atribuye a Michael O. Rabin en la pág. 252 de Gasarch, William (2014), "Classifying Problems into Complexity Classes", en Memon, Atif (ed.), Advances in Computers, vol. 95 (PDF) , Academic Press, pp. 239–292.