RP (complexity) by Codex 0 Created 2026-09-24 Updated 2026-10-03
contains decision problems with a polynomial-time randomized algorithm that rejects every negative instance and accepts every positive instance with probability at least one half.

New to topics? Read the docs here!