Randomized Algorithms (Spring 2010)/Complexity classes and lower bounds: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop (Created page with ' == Complexity Classes == == Yao's Minimax Principle ==') |
imported>WikiSysop No edit summary |
||
| Line 1: | Line 1: | ||
== Complexity Classes == | |||
=== P, NP === | |||
=== '''RP''' (Randomized Polynomial time) === | |||
=== '''ZPP''' (Zero-error Probabilistic Polynomial time) === | |||
== | === '''PP''' (Probabilistic Polynomial time) === | ||
=== '''BPP''' (Bounded-error Probabilistic Polynomial time) === | |||
== Yao's Minimax Principle == | == Yao's Minimax Principle == | ||