\documentclass{article}

\input{6045preamble}
\usepackage{amssymb,graphicx,mdwlist}

\begin{document}

\homework{9}{Nancy Lynch}{Due: Wednesday, April 18, 2007, 5PM}{Elena
  Grigorescu}

{\bf Readings:}  Sections 7.1, 7.2, 7.3

\bigskip
\begin{problem} 
(Adapted from Sipser Problems 7.1 and 7.2)
Answer each of the following with TRUE or FALSE.  You do not need to
justify your answers.  (Note: when dealing with sets like $O(f(n))$,
$\Omega(f(n))$, etc., we use the symbols $=$ and $\in$
interchangeably.) 

\bigskip
\newcounter{lastcount}
\begin{tabular}{ll}
\begin{minipage}{0.5\textwidth}
\begin{enumerate}
\item $5=O(n)$
\item $7n = O(n)$
\item $n^3 = O(n^2 \log^2(n))$
\item $n\log(n)+ 10n = O(n^2)$
\item $4^n = O(2^n)$
\item $3^n = 2^{O(n)}$
\item $2^{2^n} = O(2^{2^n})$
\item $n^n = O(n!)$
\item $n = o(2n)$
\item $2n = o(n^2)$
  \setcounter{lastcount}{\value{enumi}}
\end{enumerate}
\end{minipage}
&
\begin{minipage}{0.5\textwidth}
\begin{enumerate}
\setcounter{enumi}{\value{lastcount}}
\item $2^n = o(3^n)$
\item $1 = o(n)$
\item $n = o(\log(n))$
\item $\frac{1}{3} = o(1)$
\item $log_2(n) = \Theta(log_3(n))$
\item $2^n = \Theta(3^n)$
\item $n^5 = \Theta(32^{log_2(n)})$
\item $n^3 = \Omega(n^4)$
\item $log(n) = \Omega(log(log(n)))$
\item $3^{2^n} = \Omega(2^{3^n})$
\end{enumerate}
\end{minipage}
\end{tabular}

\end{problem}

\begin{problem}
Prove that P is closed under the following operations:
\begin{enumerate*}
\item[(a)] union,
\item[(b)] intersection,
\item[(c)] complement,
\item[(d)] concatenation.
\end{enumerate*}
P is also closed under the star operation, but that is a bit harder to
show.  (see problem 7.14).
\end{problem}

\begin{problem}
Prove that NP is closed under the following operations:
\begin{enumerate*}
\item[(a)] union, 
\item[(b)] intersection, 
\item[(c)] concatenation.
\end{enumerate*}
NP is also closed under star (see the solution to problem 7.15), but
it is not known whether NP is closed under complement.
\end{problem}


\begin{problem}
Prove that the following languages are in NP.  You may use either the
guess-and-check (certificate/verifier) method, or else describe a
nondeterministic Turing machine that decides the language in time
polynomial in the length of the input.

\begin{enumerate}
\item
NO-TRIANGLES = 
$\{\langle G \rangle|~G = (V,E) \mbox{ is an undirected graph whose
  edge set } E \mbox{ can be}$ \\$ \mbox{ partitioned into two disjoint sets } E_1 
  \mbox{ and } E_2 \mbox{ so that neither graph } (V,E_1) \mbox{ nor }
  (V,E_2)$ \\$ \mbox{ contains a triangle} \}$.

For example, the following graph is in NO-TRIANGLES  (the edges can be
split into two graphs such that neither contains a triangle; let the
bold edges be in $E_1$ and the others in $E_2$):

\begin{center}
\includegraphics[height=2.3in]{figs/hw7-1.eps}
\end{center}

The following graph is not in NO-TRIANGLES:
\begin{center}
\includegraphics[height=2.3in]{figs/hw7-2.eps}
\end{center}

\item
BOUNDED-PCP (Bounded Post Correspondence Problem), for a fixed
alphabet $\Sigma$ with $|\Sigma| \geq 2$.
This is defined as $\{ S,k |~S$ is a finite set of dominoes over
$\Sigma$, $k$ is an integer written in unary, and there is a sequence
of at most $k$ dominoes (allowing repeats) for which the top and
bottom sequences are equal$\}$.

\bigskip
If $k$ was not written in unary, would your solution to the above
still work?  Why or why not?
\end{enumerate}
\end{problem}


\end{document}


