RP (complejidad)

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

• Siempre se ejecuta en tiempo polinomial en función del 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 generar un resultado aleatorio durante su ejecución. El único caso en que el algoritmo puede devolver SÍ es si la respuesta real es SÍ; por lo tanto, si el algoritmo finaliza y produce SÍ, la respuesta correcta es definitivamente SÍ. Sin embargo, el algoritmo puede finalizar 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 las demás, entonces devolverá SÍ al menos una vez con una probabilidad de al menos 1 − 2 ^{− n} . Por lo tanto, si el algoritmo se ejecuta 100 veces, la probabilidad de que dé la respuesta incorrecta cada vez es menor que la probabilidad de que los rayos cósmicos corrompan la memoria de la computadora que ejecuta el algoritmo. ^{[ 1 ]} En este sentido, si se dispone de una fuente de números aleatorios, 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; aquí, constante significa independiente de la entrada al algoritmo.

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

• M se ejecuta en tiempo polinomial en todas las entradas.
• Para todo x en L , M produce 1 con una probabilidad mayor o igual a 1/2.
• Para todo x que no pertenece a L , M produce 0.

Alternativamente, RP puede definirse utilizando únicamente máquinas de Turing deterministas. Un lenguaje L pertenece a 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 ⁠${\displaystyle M(x,y)=1}$es mayor o igual que 1/2
• Para todo x que no está en L y para todas las cadenas y de longitud p (| x |) ,${\displaystyle 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.

La definición de RP establece que una respuesta SÍ siempre es correcta y que una respuesta NO podría 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Í podría 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 llama ZPP . Así como RP puede llamarse R , algunos autores usan el nombre co-R en lugar de co-RP .

Problema sin resolver en informática

⁠${\displaystyle {\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 P = BPP es cierta, 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 polinomial , el problema de decidir si una expresión aritmética multivariada 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 , a veces 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, independientemente del tamaño de la 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 evidente que RP es un subconjunto de NP .

• Algoritmo aleatorio

• Juego de rol en el zoológico de la complejidad