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

From TCS Wiki

Revision as of 05:26, 7 January 2010 by imported>WikiSysop

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

Jump to navigation Jump to search

Computational Models

Complexity of algorithms vs complexity of problems

Decision problems

Turing Machine

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=635"