Randomized Algorithms (Spring 2010)/Complexity classes and lower bounds: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
imported>WikiSysop
No edit summary
imported>WikiSysop
No edit summary
Line 19: Line 19:
=== '''BPP''' (Bounded-error Probabilistic Polynomial time) ===
=== '''BPP''' (Bounded-error Probabilistic Polynomial time) ===


== Yao's Minimax Principle ==
== Yao's �minimax principle ==

Revision as of 14:07, 7 January 2010

Computational Models

Upper bounds, lower bounds

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