\documentclass{article}

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

\begin{document}

\homework{7}{Nancy Lynch}{Due: April 13, 2005}{Vinod Vaikuntanathan}

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

\bigskip
\noindent
\begin{problem} 
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 $3 = O(n)$
\item $12n = O(n)$
\item $n^4 = O(n^3 \log^3(n))$
\item $3n\log(n)+ 1000n = O(n^2)$
\item $3^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(3n)$
\item $1000n = o(n^3)$
  \setcounter{lastcount}{\value{enumi}}
\end{enumerate}
\end{minipage}
&
\begin{minipage}{0.5\textwidth}
\begin{enumerate}
\setcounter{enumi}{\value{lastcount}}
\item $3^n = o(4^n)$
\item $1000 = o(n)$
\item $n = o(\log^2(n))$
\item $\frac{1}{2} = o(1)$
\item $log_2(n) = \Theta(log_{10}(n))$
\item $3^n = \Theta(4^n)$
\item $n^3 = \Theta(8^{log_2(n)})$
\item $n^2 = \Omega(n^3)$
\item $log(n) = \Omega(log(log(n)))$
\item $4^{2^n} = \Omega(2^{4^n})$
\end{enumerate}
\end{minipage}
\end{tabular}

\end{problem}

\noindent
\begin{problem}
(Sipser problem 7.12) \\
Let $$MODEXP = \{\langle a,b,c,p \rangle\ |\ \mbox{ $a,b,c$ and $p$ are
binary integers such that $a^b \equiv c\ $(mod p)} \}.$$
Show that $MODEXP$ is in $P$. (Note that the first and the most obvious
algorithm you would come up would run
in time {\em exponential in the input length}. Hint: Try it first when 
$b$ is a power of $2$.) 
\end{problem}

\noindent
\begin{problem}
(Based on Sipser problem 7.14) 
Prove that P is closed under:
\begin{enumerate}
\item
The concatenation operation.
\item
The star operation.
\end{enumerate}
\end{problem}

\noindent
\begin{problem}
Prove that NP is closed under:
\begin{enumerate}
\item
The intersection operation.
\item
The concatenation operation.
\end{enumerate}
\end{problem}

\noindent
\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.
\noindent
\begin{enumerate}
\item
(From Sipser exercise 7.11) \\
$$ISO = \{ \langle G, H \rangle | \mbox{ G and H are undirected graphs and G
and H are isomorphic }\}$$
(Two graphs are \emph{isomorphic} if, by renaming the nodes of one, we
get a graph that is identical to the other.)
\item
$TRIPLE-SAT = \{ \langle \phi \rangle | \phi \mbox{ is a Boolean formula and
$\phi$ has at least three distinct satisfying assignments }\}$
(Boolean formulas are defined on p. 271 of Sipser's book.)
\item 
A crossword puzzle construction problem is specified by a finite set 
$W \subseteq \Sigma^*$ of words, and an $n \times n$ 
matrix $A$ whose entries are either $0$ or $1$ (intuitively, a $0$
corresponds to a blank square, and a $1$ corresponds to a black
square). The goal is to use the words in $W$ to fill in the 
blank squares. Formally, suppose $E$ is the set of all 
pairs $(i,j)$ such that $A_{ij}$, the $(i,j)^{th}$ entry
of $A$, is $0$. We want to find a mapping 
$f:E \rightarrow \Sigma$ such that the letters assigned to any maximal
horizontal or vertical contiguous sequence of members of $E$ form,
in order, a word of $W$. If this is possible, we say that $(W,A)$ is 
a {\em constructable crossword system}.
$$CROSSWORD = \{(W,A)\ |\ \mbox{ $W \subseteq \Sigma^*$ and $A$ is an
$n \times n$ $0-1$ matrix and}$$ 
$$ \mbox{ $(W,A)$
is a constructable crossword system.} \}$$ 

(For instance, the set $W = \{a, b, ab, ba, aba \}$ over the alphabet $\{0,1\}$
and the matrix $A$ as in the figure form a constructable crossword system.
One of the crosswords so constructed is the matrix $B$ in the figure.
)
\begin{figure}
\includegraphics[width=5in,height=2.7in]{figs/crossword}
\end{figure}
\end{enumerate}
\end{problem}

\end{document}