\documentclass[12pt,ifthen]{article}
\usepackage{url}
\usepackage{comment}
\usepackage{amsmath, amssymb, amsthm, amstext, mathtools, graphicx, url}

\newif{\ifshowsoln}
\showsolntrue

\begin{document}

\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}

\newcommand{\CLIQ}{{\rm CLIQ}}
\newcommand{\FINDCLIQ}{{\rm FINDCLIQ}}
\newcommand{\SCLIQ}{{\rm SCLIQ}}
\newcommand{\bits}[1]{{\{0,1\}^{#1}}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\C}{{\sf C}}
\newcommand{\into}{\rightarrow}
\newcommand{\cvg}{\downarrow}
%\newcommand{\implies}{\rightarrow}
\newcommand{\st}{\mathrel{:}}

\centerline{\bf HW 7 CMSC 452. Morally Due April 16}

\centerline{\bf THIS HW IS TWO PAGES LONG!!!!!!!!!}


\begin{enumerate}

\item
(30 points)
Let

$$IS = \{ (G,k) \mid \hbox{ graph $G$ has an independent set of size $k$ } \}$$

\begin{enumerate}
\item
(10 points)
Show that $CNF$-$SAT\le IS$. Do not use CLIQUE as an intermediary.
Explain why your reduction works.
\item
(10 points)
On the formula:
$$(x_1 \vee x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2) \wedge \neg x_3$$
what $(G,k)$ does your reduction produce? Draw the graph.
\item
(10 points)
On the formula:
$$(x_1 \vee x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2) \wedge x_4$$
what $(G,k)$ does your reduction produce? Draw the graph.
\end{enumerate}


\centerline{\bf GO TO THE NEXT PAGE!!!!!!!!!!!!!!!!!!!!!}

\newpage

\item
(35 points)
Let

$$\CLIQ = \{ (G,k) \mid \hbox{ graph $G$ has a clique of size $k$ } \}$$

Let

$S\CLIQ$ be the FUNCTION that will, on input $G$, output the SIZE of the largest clique.

Let

$\FINDCLIQ$ be the FUNCTION that will, on input $G$, output both the SIZE of the largest clique,
and SOME clique of that size (that is, a list of vertices that form a clique of max size).

\begin{enumerate}
\item
(17 points)
Show that if $\CLIQ\in P$ then $\SCLIQ$ can be computed in polynomial time.
(THINK ABOUT but don't hand in: Your algorithm made several calls to the $\CLIQ$ TM.
How many? Assuming $P\ne NP$, is there a way to do with this with 18 calls to $\CLIQ$?)

\item
(18 points)
Show that if $\CLIQ\in P$ then $\FINDCLIQ$ can be computed in polynomial time.
(THINK ABOUT but don't hand in: Your algorithm made several calls to the $\CLIQ$ TM.
How many? Assuming $P\ne NP$, is there a way to do with this with 18 calls to $\CLIQ$?)
\end{enumerate}

\item
(35 points)
Let

$$3COL = \{ G \st \hbox{ graph $G$ is 3-colorable} \}.$$


Show that $3COL\le SAT$. Give an explicit reduction and explain why it works.

(HINT: Let $G$ have vertices $1,\ldots,n$.
The variables are, for $1\le i\le 3$, $1\le j\le n$,
$x_{ij}$. The variable $x_{ij}$ is intended to be TRUE if
Vertex $j$ is colored $i$, and FALSE if not.)


\end{enumerate}

\end{document}