\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Assignment $13$}
\\ NOT to be Submitted
\end{center}
\begin{quote}
To me, it does not seem unlikely that on some shelf of the universe
there lies a total book. I pray the unknown gods that some man -
even if only one man, and though it have been thousands of years
ago! - may have examined and read it. If honor and wisdom and
happiness are not for me, let them be for others. May heaven
exist, though my place be in hell. Let me be outraged and annihilated,
but may Thy enormous Library be justified, for one instant, in one
being.
\\ from The Library of Babel by Jorge Luis Borges
\end{quote}
\ben
\item Which of the following problem classes are in $P$ and
which are probably not in $P$. (By probably not we mean that
we do not as of today know that it is in $P$ but of course
tomorrow somebody might come up with a clever algorithm.)
\ben
\item {\tt PRIME}. The input here would be integers $n$ and
Yes would be returned iff $n$ is prime.
\item I gave the above problem twenty years ago. What was the
answer then?
\item {\tt CONNECTED-GRAPH}. The input here would be a graph $G$
and Yes would be returned iff the graph was connected.
\item {\tt TRAVELING-SALESMAN}.
The input here would be a graph
$G$ together with a positive integer weight $w(e)$ for each edge $e$
and an integer $B$. Yes would be returned iff there was a Hamiltonian
Cycle which had total weight at most $B$.
\item {\tt SPANNING-TREE}.
The input here would be a graph
$G$ together with a positive integer weight $w(e)$ for each edge $e$
and an integer $B$. Yes would be returned iff there was a spanning
tree which had total weight at most $B$.
\item {\tt ALMOSTDAG}.
The input here would be a directed graph $G$. Yes would be returned
iff there was a set of at most $10$ edges of $G$ that could be
removed from $G$ so that the remaining graph is a {\tt DAG}. (Your
argument should work with $10$ replaced by any {\em constant} value.)
\een
\item Show that the following problem classes are in $NP$. (That
is, describe the certificate that the Oracle gives and describe
the procedure that Verifier will take. Warning: Do not trust
Oracle! For example, if Oracle gives you $n$ distinct vertices
you have to verify that they are indeed distinct!)
\ben
\item {\tt PRIME-INTERVAL} The input here would be integers $n,a,b$.
Yes would be returned iff there was a prime $p$ which divided $n$
and for which $a\leq p\leq b$.
\item {\tt TRAVELING-SALESMAN} As described above.
\item {\tt COMPOSITE}
The input here would be an integer $n$. Yes
would be returned if $n$ was composite. For this problem I want
two solutions. One (the easier one) uses the Agarwal, Kayal, Saxena
algorithm. The second should {\em not} use the Agarwal, Kayal, Saxena
algorithm.
\item {\tt 3-COLOR}.
The input here would be a graph $G$. Yes
would be returned if there was a three coloring of the vertices
such that no two adjacent vertices $v,w$ had the same color.
\item {\tt NEAR-DAG}.
The input here would be a directed graph $G$ and an integer $B$. Yes
would be returned if there was a set of at most $B$ edges that could
be removed from $G$ so that the remaining graph was acyclic.
(This is like {\tt ALMOST-DAG} with the critical distinction that
$B$ is not restricted to $10$, or any constant value. Rather,
$B$ can depend on the number of vertices of $G$.)
\een
\item For the following pairs $L_1,L_2$ of problem classes show
that $L_1\leq_P L_2$. That is, given a ``black box" that will
solve any instance of $L_2$ in unit time, create a polynomial
time algorithm that will solve any instance of $L_1$ in polynomial
time.
\ben
\item Let $L_2$ be {\tt TRAVELLING-SALESMAN DESIGNATED PATH}.
The input here would be a graph
$G$, two designated vertices, a source $v_1$ and a sink $v_n$,
together with a positive integer weight $w(e)$ for each edge $e$
and an integer $B$. Yes would be returned iff there was a Hamiltonian
Path (i.e., one goes through all the vertices $v_1,\ldots,v_n$ in some
order (starting and ending at the designated vertices)
but does {\em not} return from $v_n$ back to $v_1$) which had total
weight at most $B$.
$L_1$ is {\tt TRAVELLING-SALESMAN} as described above.
\item
Let $L_2$ be {\tt CLIQUE}.
The input here would be a graph
$G$ together with a positive integer $B$.
Yes would be returned iff there was a clique with at least $B$
vertices.
(A set of vertices in a graph $G$ is a clique if
{\em every} pair of them are adjacent.)
Let $L_1$ be {\tt INDEPENDENT-SET}.
The input here would be a graph
$G$ together with a positive integer $B$.
Yes would be returned iff there was a independent set with at least $B$
vertices.
(A set of vertices in a graph $G$ is an independent set if
{\em no} pair of them are adjacent.)
\een
\item Assume {\tt PRIME-INTERVAL} (defined above) is in $P$. Using it as
a black box give a polynomial time algorithm with input
integer $n\geq 2$ that returns some prime factor $p$. (Caution: This
means polynomial in the number of digits in $n$, or what is sometimes
called polylog $n$, meaning $O(\lg^cn)$ for some constant $c$.)
(*) Further,
give a polynomial time algorithm with input
integer $n\geq 2$ that returns the entire prime factorization of $n$.
\een
\begin{quote}
You just keep right on thinking there Butch, thats what you're good at.
\\ Robert Redford to Paul Newman \\ {\em Butch Cassidy and the Sundance Kid}
\end{quote}
\end{document}