\documentclass{article}

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

\begin{document}

\homework{12}{Nancy Lynch}{Due: May 7, 2007}{Elena Grigorescu}

{\bf Readings:}  Section 9.1, 9.2

\bigskip

\begin{problem}
Sipser 9.13
Let $pad(s, l)$ be the function that adds enough copies of the symbol $\#$ to the end of the string $s$ so that the length of the result is at least $l$.
For any language $A$ and function $f:\mathbb{N}\rightarrow \mathbb{N}$ define the language
$$pad(A, f(m))=\{pad(s, f(m)) | \mbox{ where }s\in A, m \mbox{ is the length of } s\}.$$  
Prove that if $A\in TIME(n^6)$ then $pad(A, n^2)\in TIME(n^3)$.
\end{problem}

\begin{problem}
Sipser 9.14
%[[[Continuation of the previous problem.]]]
Prove that, if $NEXPTIME\not=EXPTIME$ then $P\not = NP$.
\end{problem}


\begin{problem}
Sipser 9.19
Define the {\bf unique-sat } problem to be
$$USAT=\{\langle \phi \rangle | \phi \mbox{ is a Boolean formula that has a single satisfying assignment}\}.$$
Show that $USAT \in P^{SAT}$.


\end{problem}

\end{document}
