\documentclass{article}

\input{6045preamble}

\begin{document}

\homework{6}{Prof. Ron Rivest}{Due: 16 April 2003}{Your Name Here}

\begin{problem} (Sipser 7.1, 7.2)
Answer each of the following with TRUE or FALSE:
(Note: when dealing with sets like $O(f(n))$ or $o(f(n))$, we use the
symbols $=$ and $\in$ interchangeably).
\begin{enumerate}
\item $2n = O(n)$
\item $n^2 = O(n)$
\item $n^3 = O(n \log^2(n))$
\item $n\log(n) = O(n^2)$
\item $3^n = 2^{O(n)}$
\item $2^{2^n} = O(2^{2^n})$
\item $n = o(2n)$
\item $2n = o(n^2)$
\item $2^n = o(3^n)$
\item $1 = o(n)$
\item $n = o(\log(n))$
\item $1 = o(1/n)$
\end{enumerate}
\end{problem}

\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}


\begin{problem} (Sipser 7.6, 7.13)
Prove that $P$ is closed under each of the following operations:
\begin{enumerate}
\item Union
\item Concatenation
\item Complement
\item Star
\end{enumerate}
\end{problem}

\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}


\begin{problem} (Sipser 7.7, 7.14)
Prove that $NP$ is closed under each of the following operations:
\begin{enumerate}
\item Union
\item Concatenation
\item Star
\end{enumerate}
\end{problem}

\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}


\begin{problem} (Sipser 7.11)
Call graphs $G$ and $H$ \emph{Isomorphic} if the nodes of $G$ can be
reordered (relabeled) so that $G$ is identical to $H$. Let 
$$
ISO = \{<G,H> | \mbox{G and H are Isomorphic Graphs} \}
$$
Prove that $ISO \in NP$. 
\end{problem}

\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}


\end{document}