\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}{2 April 2009}{18}

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

{\bf 10. Using up all Scrabble letters}

You have a set of $n$ letter tiles, each tile having exactly one
letter of the English alphabet.  (Each letter may appear multiple
times; thus you may have 5 of As, 2 of Bs, 7 of Cs, etc.)  You also
have a limited vocabulary of $m$ English words.  You want to determine
whether you can make a collection of English words that use up all of
the letter tiles, with each tile appearing exactly once in this
collection, and each word coming from your vocabulary of $m$ words.
(A word may appear multiple times in your collection.)

Show that this problem is NP-complete.

{\bf 11. Monotone QBF}

A SAT formula is set to be monotone if changing the value of any
variable from 0 to 1 does not change the value of the formula from 1
to 0; that is, increasing the value of a variable can never decrease
the value of the formula.  Suppose you are given a formula
\[
F = \exists x_1 \forall x_2 \cdots \exists x_n \phi(x_1, x_2, \ldots,
x_n),
\]
where $\phi$ is monotone.  The Monotone QBF formula is the problem of determining whether
$F$ is true.

Do one of the following: (a) Show that Monotone QBF is
PSPACE-complete; or (b) give a polynomial-time algorithm for Monotone
QBF.

\end{document}