\documentclass[12pt]{article}

\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}
\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{\N}{{\sf N}}
\newcommand{\goes}{\rightarrow}
\newcommand{\st}{\mathrel{:}}
\newcommand{\nth}{n^{th}}

\newcommand{\es}{\emptyset}

\begin{document}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\centerline{\bf Homework 7 DUE April 21 at 11:00 AM (Dead Cat April 23 at 11:00 AM)}

\begin{enumerate}

\item
(25 points)
Find a function $T(n)$ such that

$$NP \subseteq DTIME(T(n)).$$


\item
(25 points)
Construct a decidable set $A$ that is NOT in NP.
You have to construct $A$. You cannot just invoke some theorem to show $A$ exists.
(Hint: Use Problem 1.)


\item
(25 points)
Let $A,B,C$ be sets.  Show that 

if $A\le B$ and $B\le C$ then $A\le C$.

(Recall that

$X\le Y$ means that there is a polynomial time function $f$ such that

$$x\in X \hbox{ iff }f(x)\in Y.$$

)


\item
(25 points)
Let 

$$COL_c = \{ G \st \hbox{$G$ is $c$-colorable} \}.$$

\begin{enumerate}
\item
(10 points)
Show $COL_3 \le COL_4$.  (That is, there exists a function $f$ that takes a graph $G$ and
produces a graph $G'$ such that $G\in COL_3$ iff $G'\in COL_4$.)
\item
(15 points)
Show that $COL_3 \le COL_5$.
\item
(0 points) Think about: is $COL_4 \le COL_3$?
\end{enumerate}


\end{enumerate}

\end{document}