\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{comment} 

\newcommand{\DTIME}{{\rm DTIME}}
\newcommand{\NP}{{\rm NP}}
\newcommand{\DM}{{\rm DM}}
\newcommand{\VC}{{\rm VC}}
\newcommand{\IS}{{\rm ISAAC}}
\newcommand{\thCOL}{{\rm 3COL}}
\newcommand{\fourCOL}{{\rm 4COL}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}

\newcommand{\goes}{\rightarrow}
\newcommand{\nth}{n^{th}}
\newcommand{\N}{\sf{N}}
\newcommand{\Q}{\sf{Q}}
\newcommand{\R}{\sf{R}}
\newcommand{\C}{\sf{C}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\es}{\emptyset}
\newcommand{\st}{\mathrel{:}}
\newcommand{\e}{\varepsilon}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}


\begin{document}

\centerline{\bf Homework 7 (counts double)  Morally Due March 26 at 3:30PM}
\centerline{\bf Points total to 200}
\centerline{\bf Note that Spring Break is March 18-March 22}

\begin{enumerate}

\item
(0 points, but if you actually miss the midterm without telling Dr. Gasarch ahead of time, you will lose 100 points on this homework)
When will the midterm be (give date and time)?

\newpage

\item
(40 points) 
Let {\it PROMISE-SAT} be the following problem: 

\noindent
{\it Input} A boolean formula $\phi(x_1,\ldots,x_n)$
that you are PROMISED has $\ge 1$ satisfying assignment. 

\noindent
{\it Output} YES if $\phi$ has $\ge 2$ satisfying assignments
and NO if it has exactly 1 satisfying assignment.
(Because of the PROMISE $\phi$ cannot have 0 satisfying assignments.) 

\begin{enumerate}
\item 
(40 points) 
Show that IF {\it PROMISE-SAT} is in Polynomial time THEN SAT is in Polynomial time. 

{\it Hint} Here is how your proof begins:

{\it Since we are assuming {\rm PROMISE-SAT} is in polynomial time
there is a polytime Turing Machine $M$ that decides {\rm PROMISE-SAT}. 
Let $p(n)$ be the polynomial bound on $M$ (we take $n$ to be the number of vars). 
We use $M$ in the following procedure that solves SAT. We will later
analyze how long it takes. [THEN PRESENT A PROCEDURE $M$.]}

\item
(0 points but you must answer it) 
What do you THINK is true about the following problem: 
We are are promised that $\phi$ has either 0 or 1 
satisfying assignments? If THIS PROMISE-SAT problem is in P, then do you
get SAT in P? 
\end{enumerate}



\newpage


\item 
(40 points) 
Show the following: If $X\le Y$ and $Y\in P$ then $X\in P$. 


\newpage 

\item
(20 points) 

{\it Definition} Let $G=(V,E)$ be a graph. 
A {\it vertex cover for $G$ of size $k$} is a set $U\subseteq V$
such that 
\begin{itemize} 
\item 
$|U|=k$, and
\item
For every $(a,b)\in E$ either $a\in U$ or $b\in U$ (or both).
\end{itemize} 

Let $\VC = \{ (G,k) \st \hbox{$G$ has a Vertex Cover of size $k$} \}.$
(It is known that $\VC$ is NP-complete.)

Let $\VC_{1000} = \{ G \st \hbox{$G$ has a Vertex Cover of size $1000$} \}.$

\begin{enumerate}
\item
(20 points) 
Show that $\VC_{1000}$ is in P. 
\item
(0 points but I want an answer) 
The run time of your algorithm was probably $n^d$ where
$d$ is somewhat large. 
Which of the following do you THINK is true:
\begin{itemize}
\item
There are reasons to think that $\VC_{1000}$ CANNOT be solves in $O(n^3)$ time. 
\item
$VC_{1000}$ CAN be solved in $O(n^3)$ time and Bill will give his usual speech about
{\bf RESPECT HOW HARD IT IS TO OBTAIN LOWER BOUNDS! YOU HAVE TO SHOW THAT THERE IS NO CLEVER IDEA
OR HARD MATH THAT WILL SOLVE THE PROBLEM QUICKLY.}
\end{itemize} 
\end{enumerate} 


\newpage

\item 
{\it Definition} Let $G=(V,E)$ be a graph. 
A {\it dominating set for $G$ of size $k$} is a set $U\subseteq V$
such that 
\begin{itemize} 
\item 
$|U|=k$, and
\item
For every $a\in V$ either $a\in U$ or $a$ is adjacent to a vertex in $U$. 
\end{itemize} 

Let $\DM = \{ (G,k) \st \hbox{$G$ has a Dominating Set of size $k$} \}.$
(It is known that $\DM$ is NP-complete.)

Let $\DM_{1000} = \{ G \st \hbox{$G$ has a Dominating Set of size $1000$} \}.$

\begin{enumerate}
\item
(20 points)
Show that $\DM_{1000}$ is in P. 
\item
(0 points but I want a YES or NO answer) 
The run time of your algorithm was probably $n^d$ where
$d$ is somewhat large. 
Which of the following do you THINK is true:
\begin{itemize}
\item
There are reasons to think that $\DM_{1000}$ CANNOT be solves in $O(n^3)$ time. 
\item
$DM_{1000}$ CAN be solved in $O(n^3)$ time and Bill will give his usual speech about 
{\bf RESPECT HOW HARD IT IS TO OBTAIN LOWER BOUNDS! YOU HAVE TO SHOW THAT THERE IS NO CLEVER IDEA
OR HARD MATH THAT WILL SOLVE THE PROBLEM QUICKLY.}
\end{itemize} 
\end{enumerate}


\newpage

\item
(40 points) 
Let 

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

$$\fourCOL = \{ G \st \hbox{$G$ is 4-colorable } \}.$$

\begin{enumerate}
\item 
(40 points) 
Show that $\thCOL \le \fourCOL$. 

\item
(0 points but you must do it) 
What do you think about the following: 
Is $\fourCOL \le \thCOL$?
\end{enumerate} 


\newpage

\item
(40 points) 
Show that if $A\in \NP$ then there exists a polynomial $r$ such that  
$A\in \DTIME(O(2^{r(n)}))$. 

You may use that if $r_1(n)$ and $r_2(n)$ are polynomials then 
$$r_1(n) 2^{O(r_2(n))} = 2^{O(r_2(n))}.$$


\end{enumerate}

\end{document}