RP luokka

Oletetaan, että kieli L kuuluu luokkaan RP ("satunnaistettu polynomiluokka" - satunnainen polynomi), jos sen sallii todennäköisyyspohjainen Turingin kone M , jolle seuraavat ehdot täyttyvät:

• Jos w ei kuulu L:ään, niin todennäköisyys , että M myöntää w:n, on 0.
• Jos w kuuluu L:ään, niin todennäköisyys, että M myöntää w:n, on vähintään ½.
• On olemassa polynomi p(n), jolle, jos w on pituudeltaan n, niin M:n arviointi pysähtyy enintään p(n) askeleen jälkeen (satunnaisnauhan sisällöstä riippumatta).

Merkintä. RP - luokan määritelmä käyttää kahta käsitettä, jotka eivät liity toisiinsa:

• Kohdat 1 ja 2 määrittelevät satunnaistetun Turingin koneen, jota kutsutaan Monte Carlo -tyyppiseksi koneeksi .
• Kohdassa 3 puhutaan ajoajasta, joka ei riipu siitä, onko kyseinen Turingin kone Monte Carlon kone.

Merkintä. ½:n valinta kynnysarvoksi ei tässä tapauksessa ole pakollista ja tämä vakio voidaan korvata toisella (0 < < 1). Tässä tapauksessa RP sisältää samat tehtävät, mutta tiettyjen satunnaistettujen Turingin koneiden määrittämät kielet muuttuvat.

Aiheeseen liittyvät monimutkaisuusluokat

Jos Turingin kone M vastaa "Kyllä", tämä on taatusti totta, kun taas "Ei" on totta vain joissakin tapauksissa. Co-RP-monimutkaisuusluokka määritellään samalla tavalla, sillä ainoalla erolla, että vastaus "Ei" on taattu totuus ja "kyllä" ei aina ole totta. BPP - luokka kuvaa algoritmeja, jotka voivat antaa väärän vastauksen molemmissa tapauksissa. Luokkaa, joka on RP:n ja co-RP:n leikkauspiste, kutsutaan ZPP :ksi .

Suhde P:n ja NP:n kanssa

P -luokka on RP-luokan osajoukko, joka puolestaan ​​on NP -luokan osajoukko . Mukaan lukien P on Co-RP :n osajoukko, joka on Co-NP: n osajoukko . Ei kuitenkaan tiedetä tarkasti, ovatko nämä sisällytykset tiukkoja. Useimmat tutkijat ovat taipuvaisia ​​siihen versioon, että P ≠ RP tai RP ≠ NP , muuten P = NP (useimmat tutkijat ovat taipuvaisia ​​uskomaan, että tämä ei ole totta). Ei myöskään tiedetä, onko RP = Co-RP tosi , ja onko RP osajoukko NP :n ja Co-NP :n leikkauspisteestä .

Silmiinpistävä esimerkki ongelmasta, joka piilee Co-RP :ssä , mutta ei tiedetä, onko se P :ssä, on ongelma tarkistaa kahden polynomin yhtäläisyys : määrittää, onko lauseke, jossa on useita kokonaislukumuuttujia, identtinen nolla polynomi. Esimerkiksi x · x  − y · y  − ( x + y ) · ( x − y ) on identtinen nolla, kun taas x · x + y · y  ei ole.