Randomized Algorithms (Spring 2010)/Complexity classes and lower bounds

From TCS Wiki

Revision as of 14:58, 6 January 2010 by imported>WikiSysop

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to navigation Jump to search

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

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=Randomized_Algorithms_(Spring_2010)/Complexity_classes_and_lower_bounds&oldid=633"