\documentclass{article}

\input{6045preamble}
\usepackage{amssymb,amsmath,graphicx,mdwlist}

\begin{document}

\homework{8}{Nancy Lynch}{Due: April 20, 2005}{Vinod Vaikuntanathan}

{\bf Readings:}  Sections 7.4, 7.5

\bigskip

\noindent
\begin{problem} 
Let $A$ and $B$ be nontrivial languages over an alphabet $\Sigma$
(that is, not equal to $\emptyset$ or $\Sigma^*$).
Explain why each of the following is true.
\begin{enumerate}
\item
If $A$ is NP-complete, $\overline{A} \in NP$ and $B \in NP$, then
$\overline{B}$ must be in $NP$. 
\item
If $B \in P$ then $A \cap B \leq_P A$.
\item
If $B \in P$ then $A \cup B \leq_P A$.
\item
If $A \cup B$ is NP-complete, $A \in NP$ and $B \in P$, then $A$ is
NP-complete.
\end{enumerate}
\end{problem}

\noindent
\begin{problem} 
For each of the following pairs of sets $A$ and $B$, show that $A
\leq_P B$.
\begin{enumerate}
\item
$A = SAT$, and \\
$B = TRIPLE-SAT = \{ \langle \phi \rangle |~\phi \mbox{ is a satisfiable
Boolean formula that has at least }$\\ $\mbox{ three distinct satisfying
assignments }\}.$
\item
$A = VC$, the Vertex Cover problem, and \\
$B = HALF-VC$, defined as 
$\{ \langle G \rangle |~G \mbox{ is an undirected graph with an even
number of vertices, }$ \\ 
$\mbox{ of which some half form a vertex cover } \}$.
\end{enumerate}
\end{problem}

\noindent
\begin{problem} 
(Sipser 7.39)  In the proof of the Cook-Levin theorem, a window is
defined to be a 2 by 3 rectangle of cells.  Show why the proof would
have failed if we had used 2 by 2 windows instead.
\end{problem}

\noindent
\begin{problem}
(Sipser Problem 7.42)
A {\sf 2cnf-formula} is an AND of clauses, where each clause is an OR
of at most two literals. Let $2SAT = \{\langle \phi \rangle\ |\ \phi \mbox{ is
a satisfiable 2cnf-formula} \}$. Show that $2SAT \in P$.
\end{problem}

\noindent
\begin{problem} 
(Sipser 7.37)  Show that, if P=NP, it is possible to factor positive
integers into their prime factors in polynomial time. ({\sf Note:} 
NP is a class of {\em languages} and here, you are being asked
for an {\em algorithm\/} that produces a factorization for a given
integer (as opposed to deciding a language). 
Thus, simply saying that, ``because non-primality is in NP,
you are done'' isn't enough.)
\end{problem}

\end{document}