wiki_research

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

zpp (382B)

      1 # ZPP
      2 
      3 ZPP (zero-error probabilistic PTIME) = [rp] cap [corp]
      4 - you can give the correct answer or "don't know", with at most proba 1/2
      5 
      6 Corresponding algorithms for [ptime]: "Las Vegas" algorithm
      7 
      8 We know that:
      9 - ZPP contains [PTIME]
     10 - ZPP is contained in [RP] and in [coRP], which are both contained in [BPP]
     11 
     12 Up: [complexity_random]
     13 
     14 See also: [bpp], [rp], [automaton_las_vegas]