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 1: Line 1:
== Computational Models ==
== Computational Models ==


=== Complexity of algorithms vs complexity of problems ===
=== Upper bounds, lower bounds ===


=== Decision problems ===
=== Decision problems ===

Revision as of 05:26, 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=636"