RP klass

Vi kommer att anta att språket L tillhör klassen RP ("randomiserad polynomklass" - slumpmässigt polynom), om det tillåts av den probabilistiska Turing-maskinen M , för vilken följande villkor är uppfyllda:

• Om w inte tillhör L så är sannolikheten att M erkänner w 0.
• Om w tillhör L, så är sannolikheten att M erkänner w minst ½.
• Det finns ett polynom p(n) för vilket, om w har längden n, så stannar utvärderingen av M efter högst p(n) steg (oavsett innehållet på det slumpmässiga bandet).

Notera. RP -klassdefinitionen använder två begrepp som inte är relaterade:

• Punkterna 1 och 2 definierar en randomiserad Turing-maskin, som kallas en maskin av typen Monte Carlo .
• Punkt 3 talar om körtiden, som inte beror på om den givna Turing-maskinen är en Monte Carlo-maskin.

Notera. Valet av ½ som tröskel i detta fall är inte obligatoriskt och denna konstant kan ersättas med en annan (0 < < 1). I det här fallet kommer RP:n att innehålla samma uppgifter, men språken som definieras av specifika randomiserade Turing-maskiner kommer att ändras.

Relaterade klasser av komplexitet

Om Turingmaskinen M svarar "Ja" så är detta garanterat sant, medan "Nej" bara är sant i vissa fall. Co-RP-komplexitetsklassen definieras på liknande sätt, med den enda skillnaden att svaret "Nej" är en garanterad sanning, och "Ja" är inte alltid sant. BPP - klassen beskriver algoritmer som kan ge fel svar i båda fallen. Klassen som är skärningspunkten mellan RP och co-RP kallas ZPP .

Släktskap med P och NP

P - klassen är en delmängd av RP-klassen, som i sin tur är en delmängd av NP -klassen . Inklusive P är en delmängd av Co-RP , som är en delmängd av Co-NP . Det är dock inte känt exakt om dessa inneslutningar är strikta. De flesta forskare är benägna till versionen att P ≠ RP eller RP ≠ NP , annars P = NP (de flesta forskare är benägna att tro att detta inte är sant). Det är också okänt om RP = Co-RP är sant , och om RP är en delmängd av skärningspunkten mellan NP och Co-NP .

Ett slående exempel på ett problem som ligger i Co-RP , men det är inte känt om det ligger i P , är problemet med att kontrollera två polynom för likhet : för att avgöra om ett uttryck med flera heltalsvariabler är identiskt noll i ett polynom. Till exempel är x · x  − y · y  − ( x + y ) · ( x − y ) den identiska nollan, medan x · x + y · y  inte är det.