03 Other classes

Space-classes

$N T I M E (f (n)) \subseteq D S P A C E (f (n))$ .\ L, NL, polylog space, $P S P A C E = N S P A C E$ . $L \subseteq N L \subseteq P \subseteq N P \subseteq P S P A C E$ : One of these is $\subset$ : from space hierarchy theorem.

\textbf{Reachability method} on configuration graph: \ $N S P A C E (f (n)) \subseteq D T I M E (2^{f (n)})$ .

Directed reachability in $D S P A C E (l o g^{2} n)$ (Savitch) \chk. So, by reachability method: $N S P A C E (f (n)) = D S P A C E ((f (n))^{2})$ . Reachability is NL complete. \why

Immerman-Szelepcsenyi: $U n r e a c h a b i l i t y \in N L$ .\ So, coNSPACE(f(n)) = NSPACE(f(n)).

Boolean circuits

See Boolean fn ref.

Crictuit families and uniformity

Circuit family ${C_{n}}$ : Circuits for various input size. Uniformity: TM can efficiently construct ckt given input size n (on input $1^{n}$ ). Log space uniform ckt family.

P/Poly : Non uniform

$P / P o l y$ inlcudes non uniform ckts (‘advice’). $P \subseteq P / P o l y$ : Take OTM for alg; Make ckt to sync with head movements and state change.

NC and AC

$N C_{k}$ : (Nick’s class) polylog depth, uniform, bounded fan-in. Also polylog space from defn.

$A C_{k}$ : $N C_{k}$ with unbounded fanin.

Their relationship

$A C_{k} \subseteq N C_{k + 1}$ . $A C_{0} \subset N C_{1}$ : $P A R I T Y \notin A C_{0}$ \why.

$N C_{k} \subseteq L^{k}$ : just need to store current path.

PRAM

RAM model with parallel processors, shared mem. Logspace uniform family of PRAMs. Parallel computation time: f(ckt depth). $A C_{k}$ = Languages L decided by concurrent read/ concurrent write PRAM programs with polynomial procs and $O (\log^{k} n)$ time: Take ckt for L; 1 proc for each edge, 1 mem location for each gate; AND gate initialized with 1, OR gates initialized with 0.

Arithmatic

a+b $\in A C_{0} \subset N C_{1}$ : trivial ckt.

Multiplication

Find ab. $O (n^{2})$ school alg; $O (n \log n)$ FFT alg: \ $a = \sum a_{i} 2^{i} = p (2), b = q (2)$ : p and q are polynomials.

$a * b \in A C_{1}$ .

Matrix multiplication

$c_{i, j} = \sum_{k = 1}^{n} A_{i k} B_{k j}$ : both * and $\sum$ doable in $O (\log n)$ ckt: $\in N C_{1}$ .

Boolean multiplication: $c_{i, j} = \lor A_{i k} B_{k j} \in A C_{0}$ .

Matrix powering by repeated squaring: $\in N C_{2}$ .

$D E T E R M I N A N T \in N C_{2}$ : do gaussian elimination, multiply.

Boolean powering $\in A C_{1}$ : repeated squaring. So, $R E A C H A B I L I T Y \in A C_{1}$ . So, $N L \subseteq A C_{1}$ .

Randomized ckts

Random bits r, $C_{n} (x, r)$ . Contains BPP. $R N C$ : RP for NC ckts.

Non-uniformity stronger than randomness: \htext{ $B P P \subseteq P / P o l y$ }

Take BPP alg; get randomized ckt $C_{n} (x, r)$ ; reduce Pr ( $C_{n} (x, r)$ wrong for fixed x, rand r) to $2^{- n - 1}$ ; so Union bound: Pr ( rand r bad) $\leq 2^{- 1} < 1$ ; so $\exists$ r for which $C_{n} (x, r)$ correct; get deterministic ckt.

Can make $l o g_{\frac{3}{2}} n$ depth tree from any tree like ckt. So, polynomial size boolean formulae in $N C_{1}$ .

Probabilistic computation

One sided error: RP

Aka Monte Carlo alg h. RP: $P r (h (x) = 1 | x \in L) \geq 0.5$ , $P r (h (x) = 1 | x \notin L) = 0$ . Visualize the possible execution of an RP alg with computation tree: 2 types of leaves: yes or no.

Also see randomized algorithms ref. Bounding error prob p. Boosting confidence: $(1 - p)^{\frac{l}{p}} \leq e^{- l}$ . $R P \subseteq N P$ (NP has one sided error too).

2 sided error: BPP

PP: $P r (a c c e p t (x) | x \notin L) < 0.5$ . No good if $P r (a c c e p t (x) | x \notin L) = 0.5 - 2^{- O (n)}$

Also see randomized algorithms ref. $B P P \subseteq P P$ : $P r (a c c e p t (x) | x \in L) \geq 0.5$ , $P r (a c c e p t (x) | x \notin L) \leq 0.5 - \frac{1}{q (.)}$ ; 2-sided bounded error; Boosting accuracy: Run many trials, take majority; use Chernoff. $R P \subseteq B P P$ .

ZPP

$R P \cap c o R P = Z P P$ : Las Vegas alg by combining RP, coRP algs : both unsure when RP alg says $x \in L$ and coRP alg says $x \notin L$ ; (check).