\documentclass{article} \usepackage{wide} $\newcommand{\indx}{{\it index}}$ \parindent0pt

Complexity.

What is a rand. alg?

What is an alg?

Randomized algorithms have advice string, but it is random $ZPP$ (zero error probabilistic polytime) $RP$ (randomized polytime) (MC with one-sided error).

$PP$ (probabilistic polytime) (two-sided MC)

$BPP$ (bounded probabilistic polytime)

Clearly $P \subseteq RP \subseteq NP$. Open questions:

Complexity note

Adelman's Theorem.

Consider $RP$ (one sided error)

oblivious versus nonoblivious adversary and algorithms.

Game Trees

Tree evaluation.

deterministic model: must examine all leaves. time $2^h=4^{h/2}=n$

nondeterministic/checking randomized--guess which leaf wins.

Note: Changed presentation from book.

Summary: