Klassen språk som medlemskap kan bli bestemt i Polynomisk tid av en sannsynlig Turing machine med ingen falske godkjente og halvparten falske avviste. Formell definisjon: For et språk, S, finnes det en sannsynlig Turing machine, M, som godkjenner eller avviser alle strenger i Polynomisk tid. Hvis w ∉ S, M, avviser w. Hvis w ∈ S, M godtar w med en sannsynlighet minst 1/2.