%\def\solutionMode{TRUE}
\documentclass[fullpage,12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xspace}
%\usepackage{solutions}
\usepackage{enumerate}
\usepackage{fullpage}
%\setlength{\textwidth}{5.5in}
\newcounter{prcnt}
\newenvironment{problem}{\stepcounter{prcnt}{\bigskip\bigskip\bigskip\bigskip%
\hrule%
\hrule%
\hrule%
\bigskip\noindent{\underline{\bf {\large Problem \arabic{prcnt}}}} }\\}{}
\newcommand{\points}[1]{{\bf [{#1} Points]}}
\newcommand{\Term}[1]{\textsf{#1}}
\newcommand{\TermI}[1]{\Term{#1}\index{#1@\Term{#1}}}
\newcommand{\DNF}{\TermI{D{N}F}\xspace}
%\renewcommand{\P}{\mathbf{P}}
%\newcommand{\NP}{\mathbf{NP}}
%\newcommand{\coNP}{\mathbf{coNP}}
\newcommand{\pparnp}{\P_{}^\NP}
\newcommand{\pnplog}{\P^{\NP[\log]}}
\newcommand{\pnp}{\P^\NP}
\newcommand{\poly}{\ensuremath{\text{poly}}\xspace}
\newcommand{\defeq}{ \overset{\scriptscriptstyle{\rm def}}{=} }
\newcommand{\class}[1]{\ensuremath{\text{\bf{#1}}}\xspace}
\newcommand{\NP}{\class{NP}}
\renewcommand{\P}{\class{P}}
\newcommand{\coNP}{\class{coNP}}
\newcommand{\US}{\class{US}}
\newcommand{\E}{\class{E}}
\newcommand{\EXP}{\class{EXP}}
\newcommand{\polyL}{\class{polyL}}
\newcommand{\DTIME}{\class{DTIME}}
\newcommand{\DSPACE}{\class{DSPACE}}
\newcommand{\Sp}[1]{\ensuremath{\class{S}^p_{#1}}\xspace}
\newcommand{\Sigp}{\mathbf{\Sigma}^p}
\newcommand{\Sigkp}[1]{\ensuremath{\Sigp_{#1}}\xspace}
%\newcommand{\problem}[1]{\ensuremath{\text{\sf #1}}\xspace}
\newcommand{\SAT}{\problem{SAT}}
\author{}
\date{}
\begin{document}
\hrule
\begin{center}
{\Large\sc Qualifying Examination}\\[1ex]
{\sc Theoretical Computer Science}\\[1ex]
{\sc Saturday, February 28, 2009}\\[1ex]
\vspace*{0.5in}
{\Large\sc Part II: Complexity}\\
{September 18, 2009}
\end{center}
\hrule
%~
%\FullVer{\newpage}
{\bf Instructions:}
\begin{enumerate}
\item This is a closed book exam.
\item The exam is for 3 hours and has four problems of 25 points
each. Read all the problems carefully to see the order in which
you want to tackle them.
\item Write clearly and concisely. You may appeal to some standard
algorithms/facts from text books unless the problem explicitly
asks for a proof of that fact or the details of that algorithm.
\item If you cannot solve a problem, to get partial credit write
down your main idea/approach in a clear and concise way. For
example you can obtain a solution assuming a clearly stated lemma
that you believe should be true but cannot prove during the
exam. However, please do not write down a laundry list of half
baked ideas just to get partial credit.
\item Each question is worth 25 points.
\end{enumerate}
%\FullVer{\newpage}
\newcommand{\ProblemBy}[1]{{(By #1.)
\medskip
}}
\begin{problem} \ProblemBy{Lenny} Define \emph{bipolar3SAT} as the
set of Boolean formulas in 3CNF such that no clause contains both
an unnegated variable and a negated variable. Either give a
polynomialtime algorithm for finding a satisfying assignment for
a \emph{bipolar3SAT} problem, or prove that the decision problem
is NPcomplete.
\end{problem}
\begin{problem}\ProblemBy{Lenny}
Recall that a \DNF (Disjunctive Normal Form) formula is a sum (OR)
of terms, with each term a product (AND) of literals. For example,
$ A \overline{B} C + \overline{D} E F$ is a \DNF. A literal is a
variable or its negation. A \emph{monotone \DNF{}} is a \DNF where
no variable is negated.
\begin{enumerate}[(A)]
\item \points{5} What is the complexity of the following
problem? Given two \DNF formulas, determine whether or not
they represent the same function. A brief
explanation/justification is sufficient.
\item \points{20} A unate formula is one in which no variable
appears both negated and unnegated. (A special case of a
unate formula is a monotone one, in which each variable
appears only unnegated.) What is the complexity of the
following problem? Given two unate \DNF formulas, determine
whether or not they represent the same function. Prove that
your answer is correct. Partial credit is given for solving
the special case question about monotone \DNF formulas.
\end{enumerate}
\end{problem}
\newcommand{\sharpP}{{\ensuremath{\sharp\P}}\xspace}
\newcommand{\Ppoly}{{\ensuremath{\P/\poly}}\xspace}
\newcommand{\PP}{\class{PP}}
\newcommand{\Psel}{{\ensuremath{\P\text{sel}}}\xspace}
%\FullVer{\newpage}
\begin{problem}\ProblemBy{Manoj}
Recall that \PP is the class of languages of the form
\[
\{x\;\;\text{a strict majority of } w\in\{0,1\}^{m(x)} \text{ is
s.t. } R(x,w)=1\}
\]
where $m$ is some polynomial and $R$ is a polynomial time
computable relation. Also recall that \sharpP is the class of
counting functions of the form
\[
x \mapsto  \{ w\;\; w\in\{0,1\}^{m(x)} \text{and } R(x,w)=1 \}

\]
where again $m$ is some polynomial and $R$ is a polynomial time
computable relation.
Show that $\P^\PP=\P^\sharpP$.
\end{problem}
\newpage
\begin{problem}\ProblemBy{Manoj}
\begin{enumerate}[(A)]
\item \points{10} A {\em tournament} is a directed graph with a single
edge between every two nodes, directed one way or the
other. Show that in a tournament, with a vertex set $V$ of $N$
nodes (i.e., $V=N$), there is a subset of vertices $X
\subseteq V$ of size $X=O(\log N)$ such that for every
vertex $u\in V\backslash X$ there exists a vertex $v\in X$
such that there is an edge directed from $v$ to $u$.
(In other words, show that there is a small number of players
in a tournament such that every other player has defeated at
least one of them.)
\item \points{15} A function $f$ is a {\em selection function} for a
language $L$ if, on being provided with two inputs, it selects
and outputs one of the two, such that if either one or both of
the inputs are in $L$, then the output is also in $L$. That
is,
\[
f(x,y)=z \implies z \in \{x,y\} \text{ s.t. } \text{ if }
\{x,y\}\cap L \not= \emptyset \text{ then } z\in L.
\]
The complexity class \Psel is defined as the class of
languages $L$ for which there is a polynomial time computable
selection function $f$.
Show that $\Psel \subseteq \Ppoly$ (where \Ppoly is the class
of languages decidable by polynomial sized circuits, or
equivalently by nonuniform polynomial time algorithms which
take a polynomial sized advice for each input length).
\noindent{\em Hint: A selection algorithm defines a tournament
on any set of inputs. Consider the tournament over the set
of $n$bit strings in $L$.}
\end{enumerate}
\end{problem}
\end{document}