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 ==
=== Decision problems ===
=== Turing Machine ===
== Complexity Classes ==
== Complexity Classes ==


Revision as of 15:00, 6 January 2010

Computational Models

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