Problems

Let $A$ be a regular language over $\left\{ 0,1\right\}$. Show that $A$ has size-depth complexity $(O(n), O(\log n))$.

• A Boolean formula is a Boolean circuit wherein every gate has only one output wire. The same input variable may appear in multiple places of a Boolean formula. Prove that a language has a polynomial size family of formulas iff it is in $\mathrm{NC}^{1}$. Ignore uniformity considerations.

• A $\boldsymbol {k}$-head pushdown automaton ( $k$-PDA) is a deterministic pushdown automaton with $k$ read-only, two-way input heads and a read/write stack. Define the class $\mathrm{PDA}_{k}=\left\{ A \mid A\text{ is recognized by a }k\text{-PDA }\right\}$. Show that $\mathrm{P}=\bigcup_{k} \mathrm{PDA}_{k}$. (Hint: Recall that P equals alternating log space.)

Let $M$ be a probabilistic polynomial time Turing machine, and let $C$ be a language where for some fixed $0<\epsilon_{1}<\epsilon_{2}<1$,

1. $w \notin C$ implies $\operatorname {Pr}[M$ accepts $w] \leq \epsilon_{1}$, and

2. $w \in C$ implies $\operatorname {Pr}[M$ accepts $w] \geq \epsilon_{2}$.

Show that $C \in \mathrm{BPP}$. (Hint: Use the result of Lemma 10.5.)

Show that if $\mathrm{P}=\mathrm{NP}$, then $\mathrm{P}=\mathrm{PH}$.

Show that if $\mathrm{PH}=$ PSPACE, then the polynomial time hierarchy has only finitely many distinct levels.

Recall that $\mathrm{NP}^{S A T}$ is the class of languages that are decided by nondeterministic polynomial time Turing machines with an oracle for the satisfiability problem. Show that $\mathrm{NP}^{\text{SAT }}=\Sigma_{2} \mathrm{P}$.

• Prove Fermat's little theorem, which is given in Theorem 10.6. (Hint: Consider the sequence $a^{1}, a^{2}, \ldots$. What must happen, and how?)

• ᴬ Prove that for any integer $p>1$, if $p$ isn't pseudoprime, then $p$ fails the Fermat test for at least half of all numbers in $\mathcal{Z}_{p}^{+}$.

Prove that if $A$ is a language in L, a family of branching programs $(B_{1}, B_{2}, \ldots )$ exists wherein each $B_{n}$ accepts exactly the strings in $A$ of length $n$ and is bounded in size by a polynomial in $n$.

Prove that if $A$ is a regular language, a family of branching programs $(B_{1}, B_{2}, \ldots )$ exists wherein each $B_{n}$ accepts exactly the strings in $A$ of length $n$ and is bounded in size by a constant times $n$.

Show that if $\mathrm{NP} \subseteq \mathrm{BPP}$, then $\mathrm{NP}=\mathrm{RP}$.

Define a ZPP-machine to be a probabilistic Turing machine that is permitted three types of output on each of its branches: accept, reject, and ?. A ZPP-machine $M$ decides a language $A$ if $M$ outputs the correct answer on every input string $w$ (accept if $w \in A$ and reject if $w \notin A$ ) with probability at least $\frac{2}{3}$, and $M$ never outputs the wrong answer. On every input, $M$ may output ? with probability at most $\frac{1}{3}$. Furthermore, the average running time over all branches of $M$ on $w$ must be bounded by a polynomial in the length of $w$. Show that $\mathrm{RP} \cap \operatorname {coRP}=\mathrm{ZPP}$, where ZPP is the collection of languages that are recognized by ZPP-machines.

Let $\operatorname {EQ}_{\mathrm{BP}}=\left\{ \left\langle B_{1}, B_{2}\right\rangle \mid B_{1} \text{ and } B_{2} \text{ are equivalent branching programs}\right\}$. Show that $\operatorname {EQ}_{\mathrm{BP}}$ is coNP-complete.

Let BPL be the collection of languages that are decided by probabilistic log space Turing machines with error probability $\frac{1}{3}$. Prove that $\mathrm{BPL} \subseteq \mathrm{P}$.

Let $\operatorname {CNF}_{\mathrm{H}}=\left\{ \langle \phi \rangle \mid \phi \text{ is a satisfiable cnf-formula where each clause contains any number of literals, but at most one negated literal}\right\}$. Problem 7.25 asked you to show that $\operatorname {CNF}_{\mathrm{H}} \in \mathrm{P}$. Now give a log-space reduction from CIRCUIT-VALUE to $\operatorname {CNF}_{\mathrm{H}}$ to conclude that $\operatorname {CNF}_{\mathrm{H}}$ is P-complete.