In computational complexity theory, randomized polynomial time is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always runs in polynomial time in the input size If the correct answer is NO, it always returns NO If the correct answer is YES, then it returns YES with probability at least 1/2. Wikipedia