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

\newcommand{\MAXSAT}{\mbox{\sc MAX3SAT}}
\newcommand{\NP}{\mbox{NP}}

\head{CSG714}{Theory of Computation}{Spring 2008}{8 April 2008}{21}

\begin{center}
\Large{\bf Problem of the Week -- 10 and 11}
\end{center}

{\noindent \bf 10. Solving \MAXSAT}

Show that if there exists a polynomial-time approximation scheme for
$\MAXSAT$ then, in fact, $\MAXSAT$ can be solved exactly in polynomial
time.

{\noindent \bf 11. 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}
 
\end{document}