RP (complexitate)

În teoria complexității de calcul , RP ( Randomized Polynomial Time ) este clasa de complexitate a problemelor de decizie efectuate pe o mașină probabilistică de Turing .

Putem defini și o clasă foarte apropiată: co-RP .

Definiție

O primă definiție

Clasa RP este ansamblul de probleme, sau într-un mod echivalent de limbaje , pentru care există o mașină probabilistică de Turing în timp polinomial care îndeplinește următoarele condiții de acceptare:

Dacă cuvântul nu este în limbă, aparatul îl respinge.
Dacă cuvântul este în limba, aparatul îl acceptă cu o probabilitate mai mare de 1/2.

Se spune că mașina „nu funcționează decât pe o parte”.

Definiție formală

Pentru un polinom $T.$ ${\ displaystyle T}$ $T.$ cu dimensiunea de intrare $n$ ${\ displaystyle n}$ $n$ , este definit $RTIME(T(n))$ ${\ displaystyle RTIME (T (n))}$ ${\ displaystyle RTIME (T (n))}$ , setul de limbi $L$ ${\ displaystyle L}$ $L$ pentru care există o mașină probabilistică de Turing $M_{L}$ ${\ displaystyle M_ {L}}$ ${\ displaystyle M_ {L}}$ , la timp $T(n)$ ${\ displaystyle T (n)}$ $T (n)$ , astfel încât pentru fiecare cuvânt $X$ ${\ displaystyle x}$ $X$ :

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

Apoi RP poate fi definit ca: $RP=\cup _{p\in N}RTIME(n^{p})$ ${\ displaystyle RP = \ cup _ {p \ în N} RTIME (n ^ {p})}$ ${\ displaystyle RP = \ cup _ {p \ în N} RTIME (n ^ {p})}$ .

Rolul constantei

Constanta 1/2 este de fapt arbitrară, puteți alege orice număr (constant) între 0 și 1 (cu excepția) ^[1] .

Ideea este că prin efectuarea calculului independent de un număr polinomial de ori $p(n)$ ${\ displaystyle p (n)}$ $p (n)$ , poate reduce probabilitatea de eroare la $\left({\frac {1}{2}}\right)^{p(n)}$ ${\ displaystyle \ left ({\ frac {1} {2}} \ right) ^ {p (n)}}$ ${\ displaystyle \ left ({\ frac {1} {2}} \ right) ^ {p (n)}}$ În cazul în care $x\in L$ ${\ displaystyle x \ în L}$ ${\ displaystyle x \ în L}$ (în timp ce păstrează un răspuns sigur în caz $x\not \in L$ ${\ displaystyle x \ not \ în L}$ ${\ displaystyle x \ not \ în L}$ ).

Clasa co-RP

Clasa co-RP este setul de limbi pentru care există o mașină probabilistică de Turing în timp polinomial care îndeplinește următoarele condiții de acceptare:

Dacă cuvântul este în limba, aparatul îl acceptă.
Dacă cuvântul nu este în limbă, aparatul îl respinge cu o probabilitate mai mare de 1/2.

(Aceeași observație pentru constantă.)

Relațiile cu alte clase

Cu cursuri „clasice”

Avem următoarea relație cu clasele P și NP : $P\subseteq RP\subseteq NP$ ${\ displaystyle P \ subseteq RP \ subseteq NP}$ ${\ displaystyle P \ subseteq RP \ subseteq NP}$

Demonstrație

Folosim definiția unei mașini probabilistice Turing cu bandă aleatorie.

$P\subseteq RP$ ${\ displaystyle P \ subseteq RP}$ ${\ displaystyle P \ subseteq RP}$ : doar faceți calculul mașinii din P (ignorând banda aleatorie); probabilitatea de eroare este atunci zero în ambele cazuri (aparținând sau nu).

$RP\subseteq NP$ ${\ displaystyle RP \ subseteq NP}$ ${\ displaystyle RP \ subseteq NP}$ : Fie M o mașină care decide în timp polinomial $L\in RP$ ${\ displaystyle L \ în RP}$ ${\ displaystyle L \ în RP}$ . Este construită o mașină M 'de NP care oferă o bandă aleatorie astfel încât M să accepte. Dacă banda dorită chiar acceptă M, atunci M 'acceptă, altfel respinge.

Dacă există o bandă „bună”, deoarece M nu este greșit, cuvântul considerat este în $L$ ${\ displaystyle L}$ $L$ . Reciproc, dacă cuvântul este în $L$ ${\ displaystyle L}$ $L$ , M acceptă cu o probabilitate de cel puțin 1/2, adică M acceptă pe jumătate din casetele aleatorii; prin urmare, există cel puțin o bandă aleatorie care face ca aceasta să fie acceptată și, prin urmare, M 'o prevede și o acceptă.

Observăm că această clasă nu mai este interesantă dacă P = NP .

Cu celelalte clase probabiliste

Includeri de clase de complexitate probabilistică

Următoarele incluziuni pun în joc clasele ZPP și BPP .

$ZPP\subseteq RP\subseteq BPP$ ${\ displaystyle ZPP \ subseteq RP \ subseteq BPP}$ ${\ displaystyle ZPP \ subseteq RP \ subseteq BPP}$

Acest lucru rezultă direct din definiții: ZPP este intersecția dintre RP și co-RP și BPP cu condiții de acceptare mai puțin stricte (eroare „pe două fețe”).

Probleme în RP și co-RP

Cele ale RP sunt probleme pentru care există un algoritm probabilistic care îndeplinește condițiile descrise mai sus.

De exemplu, problema cunoașterii dacă un întreg este prim se află în clasa de complexitate co-RP datorită testului de primărie Miller-Rabin . De fapt, această problemă este aceeași în P , datorită testului de primărie AKS .

O problemă de co-RP care nu se știe că se află în P este problema „ testării identității polinomiale ”, care constă, dat fiind un polinom multivariat în orice formă, în a decide dacă este identic nul sau nu. Datorită lemei Schwartz-Zippel , polinoamele nule pot fi recunoscute cu o probabilitate bună prin evaluarea lor într-un număr mic de puncte.

Istorie

Clasa complexității RP a fost introdusă de John Gill ^[2] în articolul Complexitatea calculațională a mașinilor probabilistice Turing ( Gill (1977) ).

Notă

^ Arora și Barak (2009) , capitolul 7 .
^ Complexity Zoo , pe complexzozoo.uwaterloo.ca . Adus la 12 martie 2014 (arhivat din original la 21 iulie 2017) .

Bibliografie

Sanjeev Arora și Boaz Barak, Computational Complexity: A Modern Approach , Cambridge University Press , 2009, ISBN 0-521-42426-7 .
( EN ) John Gill , Computational complexity of probabilistic Turing machines , în SIAM Journal on Computing , vol. 6, nr. 4, 1977, pp. 675-695.

linkuri externe

(EN) Class RP Depus la 21 iulie 2017 în Internet Archive . pe grădina zoologică Complexity

Portal IT

Portalul de matematică

[1] Arora și Barak (2009) , capitolul 7 .

[2] Complexity Zoo , pe complexzozoo.uwaterloo.ca . Adus la 12 martie 2014 (arhivat din original la 21 iulie 2017) .

[1]

[2]