RP (složitost)

V teoretické informatiky , zejména v teorii složitosti je PR třída ( randomizované Polynomial time ) je třída složitosti z rozhodovacích problémů , pro které existuje pravděpodobnostní Turingův stroj v časovém polynomu , který odmítá všechny instance negativní a přijímá kladné instance s pravděpodobností Většího než 1/2.

Příklad

Definice

První definice

Třída RP je soubor problémů nebo ekvivalentním způsobem jazyků , pro které existuje pravděpodobnostní Turingův stroj v polynomiálním čase, který splňuje následující podmínky přijetí:

Pokud slovo není v jazyce, zařízení jej odmítne.
Pokud je slovo v jazyce, zařízení jej přijme s pravděpodobností větší než 1/2.

Říká se, že stroj „se mýlí jen na jedné straně“ .

Formální definice

Pro polynom o velikosti vstupu definujeme množinu jazyků, pro které existuje pravděpodobnostní Turingův stroj , v čase , takže pro každé slovo : $T$ $ne$ $RTIME (T (n))$ $L$ $M_ {L}$ $T (n)$ $X$

$x \ notin L \ Rightarrow Pr (M_ {L} (x) = 0) = 1$ .
$x \ in L \ Rightarrow Pr (M_ {L} (x) = 1) \ geq {\ frac {1} {2}}$ .

Takže můžeme definovat PR jako: . $RP = \ cup _ {{p \ in N}} RTIME (n ^ {p})$

Role konstanty

Konstanta 1/2 je ve skutečnosti libovolná, můžeme zvolit libovolné číslo (konstantní) mezi 0 a 1 (vyloučeno).

Myšlenka je, že provedením výpočtu nezávisle na polynomu, kolikrát , můžeme v případě snížit pravděpodobnost chyby na (při zachování bezpečné odpovědi v případě ). $p (n)$ $\ left ({\ frac {1} {2}} \ right) ^ {{p (n)}}$ $x \ v L$ $x \ ne \ v L$

Třída co-RP

Třída co-RP je sada jazyků, pro které existuje pravděpodobnostní Turingův stroj v polynomiálním čase, který splňuje následující podmínky přijetí:

Pokud je slovo v jazyce, zařízení jej přijme.
Pokud slovo není v jazyce, zařízení jej odmítne s pravděpodobností větší než 1/2.

(Stejná poznámka ke konstantě)

Vztahy s ostatními třídami

S „klasickými“ třídami

S třídou P a NP máme následující vztah : $P \ subseteq RP \ subseteq NP$

Demonstrace

Používáme definici pravděpodobnostního Turingova stroje s náhodným pásmem.

$P \ subseteq RP$ : stačí vypočítat stroj P (ignorování náhodného pásma), pravděpodobnost chyby je pak v obou případech nulová (členství nebo ne).

$RP \ subseteq NP$ : Nechť M je randomizovaný polynomiální stroj času, který rozhoduje . Postavíme stroj M ' NP, který odhaduje pásmo náhodnosti, které M přijímá. Pokud hádaná skupina skutečně přiměje M přijmout, pak M 'přijme, jinak odmítne. $L \ v RP$

Pokud existuje „dobré“ pásmo, protože M se nemýlí, uvažované slovo je v . Naopak, pokud je slovo in , M přijímá s pravděpodobností alespoň 1/2, tj. M přijímá na polovině náhodných pásem, proto existuje alespoň jedno náhodné pásmo, které jej činí akceptovatelným, a proto ho M 'odhaduje a přijímá. $L$ $L$

Tato třída již není zajímavá, pokud P = NP .

Valiant a Vazirani prokázali, že kde USAT je problém SAT, kde slibujeme, že vstupní booleovský vzorec má nanejvýš jedno řešení. Oracle na USAT funguje takto: reaguje pozitivně na vzorcích, které mají právě jedno řešení, reaguje negativně na vzorcích bez řešení, a to odpoví libovolně na jiných vzorcích. ${\ displaystyle NP \ subseteq RP ^ {USAT}}$

S ostatními pravděpodobnostními třídami

Následující zahrnutí zahrnuje třídy ZPP a BPP .

$ZPP \ subseteq RP \ subseteq BPP$

To vychází přímo z definic: ZPP je průsečík RP a co-RP a BPP má méně závazné podmínky přijetí (chyba „obou stran“).

Problémy v RP a co-RP

Problémy PR jsou problémy, pro které existuje pravděpodobnostní algoritmus, který splňuje výše popsané podmínky.

Například problém zjistit, zda je celé číslo prvočíslo, je v testu co-RP díky Miller-Rabinovu testu primality . Ve skutečnosti je tento problém dokonce v P , díky testu primitivnosti AKS .

Jeden problém co-RP , o kterém není známo, že je v P, je problém testování polynomiální identity , který zahrnuje, vzhledem k vícerozměrnému polynomu v nějaké formě, rozhodování, zda je identicky nulový nebo ne. Díky Schwartz-Zippelovmu lematu můžeme s dobrou pravděpodobností rozpoznat nulové polynomy jejich vyhodnocením na malém počtu bodů.

Dějiny

Tuto třídu představil J. Gill v článku Výpočetní složitost pravděpodobnostních Turingových strojů ( Gill 1977 ).

Bibliografie

(en) Sanjeev Arora a Boaz Barak , Výpočetní složitost: moderní přístup , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , kap. 7
(en) John Gill , „ Výpočetní složitost pravděpodobnostních Turingových strojů “ , SIAM Journal on Computing , roč. 6, n O 4,1977, str. 675-695

Externí odkaz

(fr) Třída RP v Zoo Complexity

Poznámky a odkazy

(in) Sanjeev Arora a Boaz Barak , Výpočetní složitost: moderní přístup , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , kap. 7
LG Valiant a VV Vazirani , „ NP je tak snadné jako detekce jedinečných řešení “, Theoretical Computer Science , sv. 47,1. st leden 1986,, str. 85–93 ( ISSN 0304-3975 , DOI 10.1016 / 0304-3975 (86) 90135-0 , číst online , přistupováno 11. července 2019 )
Složitost Zoo