RP ⊆ NP Inclusion · folklore Statement RP ⊆ NP: for L∈RP and x∈L, at least half of the RP machine’s polynomial-length random strings accept, and any accepting one is a certificate that a deterministic verifier checks by running the machine on it; for x∈/L none accepts — folklore.