RP (Complexitat)

En teoria de la complexitat, la classe de complexitat RP (Randomized polynomial time) és el conjunt dels problemes de decisió tals que una màquina de Turing probabilística existeix amb aquestes propietats:

• sempre s'executa amb un temps polinòmic segons la mida de l'entrada
• si la solució és NO, sempre respon NO
• si la solució és SI, retorna SI amb una probabilitat d'almenys 1/2 (en cas contrari, retorna NO)

En d'altre paraules, l'algorisme pot prendre decisions aleatòries, l'únic cas en què l'algorisme retorna SI és si la resposta correcta del problema és SI. Per tant, si la màquina acaba i respon SI, la resposta correcta és SI. Tot i això, l'algorisme pot acabar i respondre NO i estar equivocat.

La fracció d'1/2 de la definició és arbitrària i es pot canviar per qualsevol altre probabilitat menor d'1 sense que canviïn els problemes que entren dins d'aquesta classe.

Si la resposta correcta és SI i l'algorisme s'executa m cops, el resultat de cada execució és independent un de l'altra i almenys respondrà amb SI 1-2^-m cops. Així es te que si s'executa un algorisme d'aquest tipus 100 cops, la probabilitat que doni la resposta errònia cada vegada és més baixa que la probabilitat que els raigs còsmics puguin corrompre la memòria de l'ordinador executant l'algorisme. En aquest sentit, si hi ha un bona font d'atzar, molts algorismes d'aquesta classe son practicables.

Definició formal

Un llenguatge L és dins de RP si i només si existeix una màquina de Turing probabilística M tal que:

• M s'executa en temps polinòmic per qualsevol entrada
• per tot x de L, M retorna un 1 amb una probabilitat igual o major d'1/2
• per tot x no de L, M retorna un 0.

També es pot definir la classe utilitzant només màquines de Turing deterministes. Un llenguatge L és a RP si i només si existeix un temps polinòmic p i una màquina de Turing determinista tal que:

• M s'executa en temps polinòmic per qualsevol entrada
• per tot x de L, la fracció de cadenes y de longitud p(|x|) que satisfà M(x,y) = 1 és igual o major d'1/2
• per tot x no de L, totes les cadenes y de longitud p(|x|), M(x,y) = 0

A la definició, la cadena y es correspon a la sortida d'un llançament d'una moneda que la màquina de Turing probabilista pot haver fet.

Relació amb d'altres classes

La definició de RP diu que la resposta SI sempre és correcta i que la resposta NO pot estar equivocada (perquè un problema amb resposta correcta SI de vegades es pot respondre com a NO). En d'altres paraules, mentre els problemes amb resposta correcta NO sempre es responen amb un NO, no es pot confiar en la resposta NO, perquè pot ser errònia i respondre amb NO a un problema amb resposta correcta SI. La classe co-RP es defineix de forma similar, excepte que la resposta NO sempre és correcte i la resposta SI pot estar equivocada.

La classe BPP descriu algorismes que poden donar respostes incorrectes tant per problemes SI com NO i, per tant, conté tant RP com no-RP.

La intersecció de RP amb co-RP és la classe ZPP.

La classe P és un subconjunt de RP, que és un subconjunt de la classe NP. També se sap que P és un subconjunt de co-RP que és un subconjunt de la classe co-NP. No se sap si aquestes inclusions son estrictes o no.

Es conjectura que P = BPP i llavors es tindria que RP, co-RP i P col·lapsen i són iguals. Si a més s'assumeix que P ≠ NP, llavors es tindria que RP està estrictament continguda dins de NP.

Tampoc es coneix si RP = co-RP o bé si RP és un subconjunt de la intersecció de NP i co-NP, tot i que això seria una implicació si P = BPP fos cert.