wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

rp (486B)

      1 # RP
      2 
      3 Class of [decision_problem] having [algorithm_randomized] running in [ptime]
      4 with [one_sided_error]:
      5 - accept with probability 3/4 if the input is true
      6 - always reject if the input is false
      7 
      8 RP subseteq [nptime], and believed to be different
      9 
     10 Corresponding notion of [algorithm] running in [ptime]: "Monte Carlo algorithm with bounded probability of one-sided error"
     11 
     12 [rp] subseteq [bpp]
     13 
     14 Up: [complexity_random]
     15 
     16 See also: [bpp], [zpp], [corp], [automaton_monte_carlo_one_sided]