RP (complejidad) - RP (complexity)

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
No
≥ 1/2 ≤ 1/2
No 0 1
Algoritmo RP ( n ejecuciones)
Respuesta producida

Respuesta correcta
No
≥ 1 - 2 - n ≤ 2 - n
No 0 1
algoritmo co-RP (1 ejecución)
Respuesta producida

Respuesta correcta
No
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 probabilidad de al menos 1/2 (de lo contrario, devuelve 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, puede que sea incorrecto.

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 de al menos 1 - 2 - n . Entonces, si el algoritmo se ejecuta 100 veces, entonces la posibilidad de que dé una 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 1/2 se reemplaza por cualquier probabilidad constante distinta de cero menor que 1; aquí constante significa independiente de la entrada al algoritmo.

Definicion formal

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

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

Alternativamente, RP se puede definir utilizando solo máquinas de Turing deterministas. Un lenguaje L está en RP si y solo si existe un polinomio py una máquina de Turing determinista M , tal que

  • M se ejecuta por tiempo polinomial en todas las entradas
  • Para todo x en L , la fracción de cadenas y de longitud p (| x |) que satisfacen es mayor o igual a 1/2
  • Para todo x que no esté en L , y todas las cadenas y de longitud p (| x |),

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

Clases de complejidad relacionadas

Diagrama de clases de complejidad aleatorias
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 contención 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 cumplido, 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 RP y co-RP . La intersección de los conjuntos RP y co-RP se denomina ZPP . Así como RP puede llamarse R , algunos autores utilizan el nombre co-R en lugar de co-RP .

Conexión a P y NP

Problema no resuelto 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 creída P = BPP es cierta, entonces RP , co-RP y P colapsan (son todos iguales). Suponiendo además que PNP , 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 en 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 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 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 obvio el hecho de que RP es un subconjunto de NP .

Ver también

Referencias

enlaces externos