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:
| RP algoritmo por ĉiu unu ruliĝo | ||
|---|---|---|
| Redonita respondo | ||
| Ĝusta respondo | Jes | Ne |
| Jes | ≥ 1/2 | ≤ 1/2 |
| Ne | 0 | 1 |
| RP algoritmo por n ruliĝoj | ||
| Redonita respondo | ||
| Ĝusta respondo | Jes | Ne |
| Jes | ≥ 1 - (1/2)n | ≤ (1/2)n |
| Ne | 0 | 1 |
| co-RP algoritmo por ĉiu unu ruliĝo | ||
| Redonita respondo | ||
| Ĝusta respondo | Jes | Ne |
| Jes | 1 | 0 |
| Ne | ≤ 1/2 | ≥ 1/2 |
| co-RP algoritmo por n ruliĝoj | ||
| Redonita respondo | ||
| Ĝusta respondo | Jes | Ne |
| Jes | 1 | 0 |
| Ne | ≤ (1/2)n | ≥ 1 - (1/2)n |
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
[redakti | redakti fonton]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
[redakti | redakti fonton]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ŭ
[redakti | redakti fonton]- Hazardigita algoritmo
- Primeco-testo de Solovay-Strassen - ekzemplo de la algoritmo
