RP (komplikeco)

En komputa komplikteorio, **RP** (iam nomata **R**) ("hazardigita polinoma tempo") estas komplikeco-klaso de decido-problemoj, kiuj povas esti solvitaj per probableca maŝino de Turing en polinoma tempo kun ĉi tiuj probablecoj de la rezultoj:

Alivorte, tia algoritmo havu jenajn ecojn:
* Ĝi ĉiam ruliĝas en tempo polinoma tilate al la amplekso de la enigo.
* Se la ĝusta respondo estas "ne", ĝi ĉiam redonas respondon "ne".
* Se la ĝusta respondo estas "jes", tiam ĝi redonas respondon "jes" kun probablo almenaŭ 1/2 (alie, ĝi redonas respondon "ne").

Tiel la sola okazo, en kiu la algoritmo povas redoni respondon "jes", estas, se la ĝusta respondo estas "jes". Pro tio, se la algoritmo redonas respondon "jes", la ĝusta respondo estas definitive "jes". Tamen, se la algoritmo redonas respondon "ne", la ĝusta respondo ankoraŭ ne estas sciata.

Se la ĝusta respondo estas "jes" kaj la algoritmo ruliĝas *n* fojojn kun la rezultoj de la ruliĝoj statistike sendependaj unu de la aliaj, tiam ĝi redonas respondon "jes" almenaŭ unufoje kun probablo almenaŭ 1 - (1/2)n.

Kutime la algoritmo, krom la ĉefa enigo, prenas iun hazardan variablon, de kies valoro la rezulto dependas en la necerta okazo. Kutima uzo de ĉi tiaj algoritmoj estas jena:

* Ruli la algoritmon multfoje, ĉiufoje kun la nova valoro de la hazarda variablo.
* Se almenaŭ unu redonita respondo estas "jes", eblas konkludi, ke la ĝusta respondo efektive estas "jes".
* Se ĉiam redonita respondo estas "ne", la ĝusta respondo preskaŭ certe estas "ne".

Tiel, se la algoritmo ruliĝas 200 fojojn, tiam la ŝanco ricevi eraran respondon estas malpli granda, ol la ŝanco, ke kosma radiado fuŝas memoron de la komputilo. En ĉi tiu senco, se fonto de stokastoj estas havebla, plejparto de ĉi tiaj algoritmoj estas praktike uzebla.

La frakcio 1/2 en la difino povas esti anstataŭigita per iu ajn la alia *p*, *0<p<1*, la aro **RP** de la ŝanĝo ne ŝanĝiĝas. Necesas nur konforme alĝustigi la kvantn de ruliĝoj de la algoritmo por la sama probableco de eraro, kaj la kvanto ne dependas de la amplekso de la enigo kaj tiel la ordo de rula tempo ne ŝanĝiĝas.

## Rilataj komplikeco-klasoj 
Laŭ la difino, por algoritmo el la klaso **RP** la respondo *jes* ĉiam estas ĝusta kaj la respondo *ne* ne ĉiam estas ĝusta. Simile, por algoritmo el la klaso **co-RP** (iam nomata **co-R**) la respondo *ne* ĉiam estas ĝusta kaj la respondo *jes* ne ĉiam estas ĝusta.

La komunaĵo de la aroj **RP** kaj **co-RP** estas **ZPP**. Tiel la **ZPP** estas klaso de algoritmoj kiuj povas doni malĝustan respondon en ne pli ol unu el la du okazoj.

La klaso **BPP** estas de algoritmoj kiuj povas doni malĝustan respondon en ambaŭ la jesa kaj la nea okazoj.

### RP kaj P kaj NP 
**P** estas subaro de **RP** kaj **RP** estas subaro de **NP**. Simile, **P** estas subaro de **co-RP** kaj **co-RP** estas subaro de **co-NP**. Ne estas sciate ĉu ĉi tiuj subaroj estas severaj. Tamen, oni ĝenerale kredas, ke **P** ≠ **NP**, kaj pro tio **P** ≠ **RP** aŭ **RP** ≠ **NP**. Ne estas sciate, ĉu **RP** = **co-RP**. Ankaŭ ne estas sciate, ĉu **RP** estas subaro de la komunaĵo de **NP** kaj **co-NP**.

Ekzemplo de problemo, por kiu estas sciata **co-RP** algoritmo sed nun ne estas sciata **P** algoritmo, estas problemo decidanta, ĉu donita multvariabla aritmetika esprimo super entjeroj estas la nula polinomo. Ekzemple, *x·x-y·y-(x+y)·(x-y)* estas la nula polinomo sed *x·x+y·y* ne estas.

Alia karakterizo de algoritmo de **RP** estas tio, ke nedeterminisma maŝino de Turing donas ĝustan respondon almenaŭ iu frakcio el la kalkuladaj vojoj, kaj la frakcio estas sendependa de la eniga amplekso. Ĉe algoritmo de **NP**, sufiĉas ke la certan veran respondon donas almenaŭ unu vojo, kaj ĉi tiu unu vojo povas konsistigi eksponente malgrandan frakcion de la eblaj vojoj. Tiel videblas ke **RP** estas subaro de **NP**.

## Vidu ankaŭ 
* Hazardigita algoritmo
* Primeco-testo de Solovay-Strassen - ekzemplo de la algoritmo

Kategorio:Komputa komplikeco