\documentclass{article}

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

%%% STUDENTS - uncomment the newcommand line below to get your
%%%   LaTex to compile correctly.  I added this to
%%%   my 6045preamble file to make typing easier.
\newcommand{\brk}[1]{\langle #1 \rangle}

\begin{document}

\homework{9}{Nancy Lynch}{Due: May 4, 2005}{Vinod Vaikuntanathan}

\bigskip
\noindent
{\bf Readings:}  Sipser, Section 7.5.  Also (optionally) see Garey and
Johnson's book, ``Computers and Intractability:  a Guide to
NP-Completeness''.

\bigskip
\noindent
\begin{problem} (Sipser 7.20) Let $G$ represent an undirected graph
and let 
$$\mbox{\sf SPATH} = \{\brk{G,a,b,k}|~G \mbox{ 
contains a simple path of
length at {\bf most} $k$ from $a$ to $b$}\}$$ and

$$\mbox{ \sf LPATH}=\{\brk{G,a,b,k}|~G \mbox{ contains a simple path of length at
{\bf least} $k$ from $a$ to $b$}\}$$
\begin{enumerate}
\item Show that {\sf SPATH} $\in$ P. 
\item Show that {\sf LPATH} is NP-complete.  You may assume the
NP-completeness of {\sf UHAMPATH}, the Hamiltonian path problem for
undirected graphs.
\end{enumerate}
\end{problem}

\noindent
\begin{problem} 
For a cnf-formula $\phi$ with $m$ variables and $c$ clauses,
show that you can construct in polynomial time an NFA with 
$O(cm)$ states that accepts all non-satisfying assignments,
represented as Boolean strings of length $m$. Conclude that
the problem of minimizing NFAs cannot be done in polynomial
time unless $P = NP$. 
\end{problem}

\noindent
\begin{problem} 
An edge-cover in a graph $G(V,E)$ is a set of edges 
$E' \subseteq E$ of $G$ 
such that each vertex in $G$ is the end-point of at least one of the 
edges in $E'$. As a language,  
$$\mbox{\sf EDGE-COVER} = \{\langle G,k \rangle \ |\ G \mbox{ is an
undirected graph that has an edge-cover with at most $k$ edges} \}.$$
Show that {\sf EDGE-COVER} $\in P$.
(Recall the problem {\sf VERTEX-COVER} that we proved NP-complete
in the class.)

({\sf Hint:} You can assume, without proof, 
that the problem of finding a maximum
matching in a graph is in $P$. In a graph $G=(V,E)$, a 
matching is a set $E' \subseteq E$ of edges, such  that no two 
edges in $E'$ are adjacent to the same vertex. A maximum matching 
in $G$ is such a set $E'$ of the largest cardinality.
Use a maximum matching to construct a minimum edge-cover, and prove
that your construction works, and runs in polynomial time.) 
\end{problem}

\noindent
\begin{problem}
Suppose there exists a family of bijections $\{f_k\}_{k=1}{\infty}$ such that
$f_k$ maps integers of length $k$
onto integers of length $k$. We also know that  
\begin{itemize}
\item For all $k$, $f_k$ is computable in polynomial time (in $k$), and
\item No $f^{-1}_k$ is computable in polynomial time.
\end{itemize}
Prove that this would imply that the language 
$$ A = \{\langle x,y \rangle \ | \ f^{-1}(x) < y \}$$ 
is in ({\sf NP} $\cap$ {\sf coNP}) $-$ {\sf P}.
\end{problem}
\end{document}