[bodhiandphysics]

it can be probably polynomial time... that's ZPP! (ZPP is the complexity class of languages that are accepted by a randomized turing machine in expected polynomial time. However, in the worst case, the turing machine is allowed to take arbitrary time). In ZPP note the error probability is 0... it always returns YES or NO correctly.

It's unknown whether ZPP = P (but it almost certainly does). It is known that ZPP is the base of the random hierarchy... ZPP = RP u co-RP, where RP is the class of languages that are accepted with bounded error.

Any good complexity textbook beyond Sipser will discuss the randomized complexity classes at extreme detail, since they are crucial for constructing all the other interesting complexity classes (notably IP and MIP).

[ot]

Sure, there are plenty of complexity classes :) but TFA is about derandomization of BPP, even if it doesn't mention the class by name, it talks about Nisan-Widgerson.