\documentclass{article}
\input{6045preamble}
\newcommand{\spacechar}{\sqcup}
\newcommand{\length}[1]{\left \vert #1 \right \vert}

\begin{document}
\homework{7}{Prof. Ron Rivest}{Due: 17 April 2002}{}

\begin{problem}
  \begin{enumerate}
  \item Exercise 7.6
  \item Prove or disprove: if $L \in \P$ and $L' \subseteq L$, then
    $L' \in \P$. 
  \end{enumerate}
\end{problem}

\begin{problem}
  \begin{enumerate}
  \item Exercise 7.7
  \item Prove or disprove: if $L \in \NP$ and $L' \subseteq L$, then
    $L' \in \NP$. 
  \item   Show that if $f = O(g)$ and $g = O(h)$ then $f = O(h)$
  \end{enumerate}
\end{problem}

\begin{problem}
  Exercise 7.10. Note that ``polynomial'' here means polynomial in the
  number of nodes in the graph. You can assume that the length of the
  representation of the graph is already polynomial in this sense.
\end{problem}


\begin{problem}
  For any function $t(n)$, show that there is a decidable language $L$
  which cannot be decided in running time $t$. That is, show that
  there exists a word $w$ so that $w \in L$ cannot be decided in time
  $t(\length{w})$. (Hint: consider the language of machine/word pairs
  $\rep{M,w}$ such that $M$ does not accept the word $w$ in less than
  $t(\length{w})$ steps.)
\end{problem}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
% LocalWords:  Undecidability
