Rp Randomized polynomial time is de complexiteitsklasse van de computationele complexiteitstheorie, problemen waarvoor een probabilistische Turingmachine bestaat met deze eigenschappen:⁕het draait altijd in polynomiale tijd in de invoergrootte⁕als het juiste antwoord nee is, geeft het altijd Nee terug⁕als het juiste antwoord ja is, dan geeft het ja terug met een waarschijnlijkheid van minstens 1/2. met andere woorden, het algoritme mag een echt willekeurige munt omdraaien terwijl het draait. Het enige geval waarin het algoritme Ja kan retourneren is als het werkelijke antwoord ja is; daarom als het algoritme eindigt en ja produceert, dan is het juiste antwoord Zeker ja; echter, het algoritme kan eindigen met nee, ongeacht het werkelijke antwoord. Dat wil zeggen, als het algoritme geeft Nee, Het kan verkeerd zijn.Sommige auteurs noemen deze klasse R, hoewel deze naam vaker wordt gebruikt voor de klasse van recursieve talen.Als het juiste antwoord ja is en het algoritme n keer wordt uitgevoerd met het resultaat van elke run statistisch onafhankelijk van de andere, dan zal het ten minste eenmaal met een kans van ten minste 1 − 2−ja retourneren. Dus als het algoritme 100 keer wordt uitgevoerd, dan is de kans dat het elke keer het verkeerde antwoord geeft kleiner dan de kans dat kosmische stralen het geheugen van de computer waarop het algoritme draait, hebben beschadigd. In deze zin, als een bron van willekeurige getallen beschikbaar is, zijn de meeste algoritmen in RP zeer praktisch.

zie meer “