\documentclass{article}

\input{6045preamble}

\begin{document}

\homework{7}{Prof. Ron Rivest}{Due: 23 April 2003}{Your Name Here}

\begin{problem} \textbf{Polynomial-Time Reductions} 

\textbf{Part A:}
The Traveling Salesman Problem (TSP) is: Given a set of $n$ cities,
the pairwise distances between the cities and an integer $k$, determine
if there is a tour that starts in city 1, visits each other city exactly once
and ends in city 1, where the total length of the cycle is at most $k$. 
(Formally, TSP is defined as a set of pairs, $<D,k>$, such that $D$ is an $n$x$n$
matrix containing the distances between each pair of cities and 
the $n$ cities defined by $D$ contain a TSP tour of total
length at most $k$). 

The Hamiltonian Cycle Problem (HAMCYCLE) is: Given a graph, determine whether there
exists a cycle (a path with the same starting and ending point) which visits each
vertex exactly once. (Formally, HAMCYCLE is a set of graphs, $<G>$, that contain
a Hamiltonain Cycle).

Prove that $HAMCYCLE \leq_p TSP$. (Note: Since HAMCYCLE is NP-Complete, this reduction
proves the NP-Completeness of TSP).

\textbf{Part B:} (Sipser 7.19)
The DOUBLE-SAT problem is: 
$$
DOUBLE-SAT = \{<\phi> | \phi \mbox{ is a boolean formula which has at least two 
                              distinct satisfying assignments} \}
$$
Prove that $SAT \leq_p DOUBLE-SAT$ (Note: This also proves that DOUBLE-SAT is
NP-Complete).

\textbf{Part C:}
The ODD-ONES problem is:
$$
ODD-ONES = \{ s \in \{0,1\}^* | s \mbox{ contains an odd number of 1's } \}
$$
Prove that $ODD-ONES \leq_p 3COL$ (Note: This does not prove that ODD-ONES
is NP-Complete)

\end{problem}

\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}

\begin{problem} \textbf{The Cook-Levin Theorem} 

\textbf{Part A:} (Sipser 7.32)
When proving the Cook-Levin theorem, we defined a window
to be a 2x3 rectangle of cells. Show that the proof would have failed
if we used a 2x2 window instead. (Note: A similar argument shows
that the proof would have failed if we used kx2 windows for any $k$).

\textbf{Part B:} 
When proving the Cook-Levin theorem, we 
defined a window to be a 2x3 rectangle of cells. In Part A of this
problem you showed that a smaller rectangle would not have worked. 
In this part, we consider using a much larger rectangle of cells.
Let $n^k$x$n^k$ be the size of the entire tableau, show that the proof
would have failed if we had used an $n$x3 window.
\end{problem}

\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}

\end{document}