\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\PH}{\mbox{PH}}
\newcommand{\NP}{\mbox{NP}}

\head{CSG714}{Theory of Computation}{Spring 2009}{24 March 2009}{16}

\begin{center}
\Large{\bf Problems of the Week -- 7, 8, and 9}
\end{center}

{\noindent \bf 7. Solving TQBF blindfolded with two oracles}

Problem 9.22 of Sipser.  Suppose you are given two Turing machines $A$
and $B$, one of which is known to decide TQBF (i.e., given a QBF
formula $F$, it accepts if $F$ is true, and rejects otherwise), but
you don't know which.  (You have no information of what the other
machine does.) Give an algorithm that access to both $A$ and $B$ and
is guaranteed to solve TQBF in polynomial time.

{\noindent \bf 8. Branching programs}

\begin{itemize}
\item[{\bf (a)}]
Show that any boolean function over $n$ boolean inputs can be computed
by a branching program with $O(2^n)$ nodes.

\item[{\bf (b)}]
Show that if one can test in polynomial time whether two branching
programs compute the same function, then $\mbox{P} = \NP$.  Is the same
true for read-once branching programs?
\end{itemize}

{\noindent {\bf 9. Complete problems in \PH}}

Prove that $\PH$ has a problem that is complete for $\PH$ with respect
to polynomial time reductions if and only if there exists $k \ge 0$
such that $\PH = \Sigma_k^P$.
\end{document}
