\documentclass{article}

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

\begin{document}

\homework{10}{Nancy Lynch}{Due: April 23, 2007}{Elena Grigorescu}

{\bf Readings:}  Sections 7.4, 7.5

\bigskip

\begin{problem} 

Let $A$ and $B$ be nontrivial languages over an alphabet $\Sigma$ (that
is, not equal to $\emptyset$ or $\Sigma^*$).
State whether each of the following is KNOWN TO BE TRUE, KNOWN TO BE
FALSE, or UNKNOWN.  Explain carefully why.  For example if you claim
that a reduction exists, then you should actually define
the reduction.
\begin{enumerate}
\item
If $A \leq_P B$, then $\overline{A} \leq_P \overline{B}$.
\item
If $B \in P$ and $A$ is nontrivial (not equal to $\emptyset$ or
$\Sigma^*$), then $A \cap B \leq_P A$.

\item
If $B \in P$ and $A$ is nontrivial, then $A \cup B \leq_P A$.

\item
If $A \cap B$ is NP-complete, $A \in NP$ and $B \in P$, then $A$ must be
NP-complete.
\item
If $A \cup B$ is NP-complete, $A \in NP$ and $B \in P$, then $A$ must be
NP-complete.
\item
If $A$ is NP-complete, $\overline{A} \in NP$ and $B \in NP$, then
$\overline{B}$ must be in $NP$. 
\item
If $A$ is NP-complete, $\overline{A} \in NP$ and $B \in NP$, then
$\overline{B}$ must be in $P$.
\end{enumerate}
\end{problem}

\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 = SAT$-$UNSAT = \{ \langle \phi \rangle |~\phi$ is a satisfiable Boolean formula that is not
a tautology (that is, it has at least one non-satisfying
assignment)$\}$;
\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}


\end{document}


