Exercises

Show that a circuit family with depth $O(\log n)$ is also a polynomial size circuit family.

Show that 12 is not pseudoprime because it fails some Fermat test.

Prove that if $A \leq_{\mathrm{L}} B$ and $B$ is in NC, then $A$ is in NC.

Show that the parity function with $n$ inputs can be computed by a branching program that has $O(n)$ nodes.

Show that the majority function with $n$ inputs can be computed by a branching program that has $O\left(n^{2}\right)$ nodes.

Show that any function with $n$ inputs can be computed by a branching program that has $O\left(2^{n}\right)$ nodes.

ᴬ Show that $\mathrm{BPP} \subseteq \mathrm{PSPACE}$.