\documentclass{article}
\input{6045preamble}


\begin{document}
\handout{14}{Prof. Ron Rivest}{18 April 2002}{Jonathan
  Herzog}{Handout 14: Recitation Problems}

Which of the following are valid?

\begin{enumerate}

 
\item Let $$\mathit{SAT} = \cset{\phi}{\phi \mbox{ has a satisfying
      assignment }}$$ and $$\mathit{DoubleSAT} = \cset{\phi}{\phi
    \mbox{ has at least two satisfying assignments }}.$$ Consider the function
  from boolean formulae to boolean formulae given by:
  $$t(\phi) = \phi \wedge ( x \vee \overline{x})$$
  where $x$ is a variable not otherwise occurring in $\phi$.   
  
  The function $t$ is a mapping from $\mathit{SAT}$ to
  $\mathit{DoubleSAT}$ and so
  $$\mathit{SAT} \pred \mathit{DoubleSAT}$$


\item Let 
  $$\mathit{TRIANGLE} = \cset{G}{G \mbox{ has a clique of size 3}}$$
  and
  $$\mathit{HAMCYCLE} = \cset{G}{G \mbox{ has a Hamiltonian cycle }}.$$
  Consider the function from graphs to graphs 
  given by:
  $$t(G) = \left \{
    \begin{array}{l}
      \mbox{ if $G$ has a triangle, that triangle}\\
      \mbox{ if $G$ does not have a triangle, the sub-graph of $G$
        formed by its first 3 nodes}
    \end{array}
    \right.
    $$

  
  The function $t$ is a mapping from $\mathit{TRIANGLE}$ to
  $\mathit{HAMCYCLE}$ and so
  $$\mathit{TRIANGLE} \pred \mathit{HAMCYCLE}$$

  
\item Consider the function from boolean formulae to graphs given by:
  $$t(\phi) = \left \{
    \begin{array}{l}
      \mbox{ if $\phi$ has a satisfying assignment, a triangle}\\
      \mbox{ if $\phi$ has no satisfying assignment, a triangle missing
        one edge}
    \end{array}
    \right.
    $$

  
  The function $t$ is a mapping from $\mathit{SAT}$ to
  $\mathit{TRIANGLE}$ and so
  $$\mathit{SAT} \pred \mathit{TRIANGLE}$$

  

\end{enumerate}

\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
