RP (komplikeco)
En komputa komplikteorio, RP (iam nomata kiel R) ("hazardigita polinoma tempo") estas komplikeca klaso de decidaj 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, la algoritmo havas jenajn propraĵojn:
- Ĝi ĉiam ruliĝas en polinoma tempo en la eniga amplekso.
- Se la ĝusta respondo estas "ne", ĝi ĉiam redonas respondon "ne".
- Se la ĝusta respondo estas "jes", tiam ĝi redonas respondon "jes" kun probablo minimume 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", do la ĝusta respondo estas definitive "jes". Tamen, se la algoritmo redonas respondon "ne", la ĝusta respondo ne estas ankoraŭ sciata.
Se la ĝusta respondo estas "jes" kaj la algoritmo estas ruliĝas n fojojn kun la rezultoj de la ruliĝoj estas 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 valoro de kiu dependas la rezulto en la necerta okazo. Kutima uzo ĉi tiaj algoritmoj estas jena:
- Riligi la algoritmon multfoje, ĉiu foje kun la nova valoro de la hazarda variablo.
- Se almenaŭ unu redonita respondo estas "jes" do opinii ke la ĝusta respondo estas "jes" (certe).
- Se ĉiam redonita respondo estas "ne" do opinii ke la ĝusta respondo estas "ne" (preskaŭ certe).
Tiel se la algoritmo ruliĝas 200 fojojn do la ŝanco de ricevo de la erara respondo estas pli malgranda ol la ŝanco ke kosma radiado fuŝas memoron de la komputilo. En ĉi tiu senco, se fonto de stokastoj estas havebla, plej parto de ĉi tiaj algoritmoj estas praktika.
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. Nur bezonatas la alia kvanto de riliĝ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..
Rilatantaj komplikecaj klasoj
[redakti | redakti fonton]Laŭ la difino, algoritmo el klaso RP diras ke jes ĉiam ĝuste kaj ke ne iam ĝuste. Simile, algoritmo el klaso co-RP (iam nomata kiel co-R) diras ke ne ĉiam ĝuste kaj ke jes iam ĝuste.
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 ne 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 de 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 tia ke sur nedeterminisma maŝino de Turing la certan veran respondon donas 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