|
gptkbp:instanceOf
|
gptkb:theoretical_computer_science
|
|
gptkbp:acceptanceProbability
|
0 for no-instances
at least 1/2 for yes-instances
|
|
gptkbp:characterizedBy
|
randomized algorithms
|
|
gptkbp:closed
|
closed under intersection
closed under union
|
|
gptkbp:computationTime
|
polynomial time
|
|
gptkbp:contains
|
gptkb:decision_problems
|
|
gptkbp:definedIn
|
gptkb:theoretical_computer_science
|
|
gptkbp:errorDetection
|
false negatives not allowed
false positives allowed
|
|
gptkbp:example
|
Polynomial identity testing
Primality testing (historically, before deterministic algorithms)
|
|
gptkbp:hasSubgroup
|
gptkb:BPP
NP
|
|
gptkbp:hasWikipediaPage
|
https://en.wikipedia.org/wiki/RP_(complexity)
|
|
gptkbp:introduced
|
gptkb:Michael_O._Rabin
|
|
gptkbp:introducedIn
|
1976
|
|
gptkbp:randomnessType
|
one-sided error
|
|
gptkbp:relatedTo
|
gptkb:co-RP
gptkb:ZPP
P
NP
|
|
gptkbp:standsFor
|
Randomized Polynomial time
|
|
gptkbp:bfsParent
|
gptkb:NP_(complexity_class)
gptkb:P_(complexity_class)
|
|
gptkbp:bfsLayer
|
6
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
RP (complexity class)
|