\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,graphics}

\setlength{\textwidth}{7in}
\setlength{\topmargin}{-0.575in}
\setlength{\textheight}{9.25in}
\setlength{\oddsidemargin}{-.25in}
\setlength{\evensidemargin}{-.25in}

\reversemarginpar
\setlength{\marginparsep}{-15mm}

\newcommand{\rmv}[1]{}
\newcommand{\bemph}[1]{{\bfseries\itshape#1}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\imply}{\to}
\newcommand{\bic}{\leftrightarrow}

% Here the user must define certain strings for this homework assignment
%
\def\CourseCode{COMP 6902}		% e.g. B38
\def\AssignmentNo{2}			% e.g. 1
\def\DateHandedOut{Spring, 2018}	% e.g. September 18, 2002
\def\DateDue{June 15, 2018}		% e.g. October 1, 2002
\def\TimeDue{7:00am}			% e.g. 11 am

\begin{document}

\noindent
\rmv{Computer Science }
\CourseCode \hfill \DateHandedOut\\

\begin{center}
Homework Assignment \#\AssignmentNo\\
Due: \DateDue, by \TimeDue\\

Please typeset the assignment in LaTeX, and upload the pdf file on D2L. \\

\medskip

%%%%%%  M A K E    S U R E    T O     W R I T E    Y O U R    N A M E    H E R E!!!  %%%%%%%%%%%%%%%

\textbf{YOUR NAME HERE} \\


\end{center}

\hrule\smallskip




\begin{enumerate}


\item  Suppose \marginpar{[10]}
 that  $L_1 \leq_p L_2$ and  $L_2 \leq_p L_3$. Also suppose that $L_3$ is  in NP.  Explain how to solve $L_1$ deterministically in \emph{exponential} time  using  polynomial space.



{\em Solution: 



} 





\item Prove that  \marginpar{[75]} the problems below are NP-complete.
You can assume that the following problems are NP-complete: 3SAT, HamPath,
Partition, Clique, and $\neq$SAT.  Make sure you show that the problems are in NP,  then give respective reductions and give an "if and only if" argument for reduction correctness, as well as say why your reduction runs in polynomial time. 

\begin{enumerate}
\item  \textbf{Two-Long-Paths:} 
\(TLP=\{ \langle G \rangle | G\)   has two paths on at least  \( \lfloor n/2 \rfloor\) vertices each$\}$


{\em Solution: 




} 





\item \textbf{Quarter Partition}
\( QP =\{\langle a_1,\dots,a_n \rangle | \forall i, a_i \geq 0,\) and  $a_1 \dots 
a_n$ can be partitioned into two disjoint sets $S$ and $\bar{S}$ and such that 
\( \Sigma_ {a_i \in S} a_i = \Sigma_ {a_i \in \bar{S} } a_i\) and, moreover, $|S|=\lfloor n/4 \rfloor  \}$



{\em Solution: 



} 





\item \textbf{QuadSat:}
\( QuadSat = \{\langle \phi \rangle | \phi \) is a satisfiable 3CNF formula with at least 4 satisfying assignments$\}$.



{\em Solution: 



} 





\item  \textbf{k-Clique HamPath:}  
\(kCHP=\{ \langle G,k \rangle | G \) is an undirected graph and $k
\in \mathbb{N}$, and $G$ contains both a clique of size $k$ and a Hamiltonian path$ \}$.  



{\em Solution: 



} 





\item  \textbf{Representatives:}  
\(Rep=\{ \langle S_1, \dots, S_m,  k  \rangle | S_1, \dots, S_m  \) are subsets of some set $U$ with  $|U|=n$,   $k
\in \mathbb{N}$, and there is a set $S \subseteq  U$, $|S| \leq k$,  which contains at least one element from each of  $S_i  \}$.  


{\em Solution: 



} 







\end{enumerate}


\item Prove \marginpar{[15]} that the following problems are solvable in
polynomial time by describing (in words) algorithms that solve them. State the
complexity of your algorithms in $O$-notation. 
\begin{enumerate}
\item \textbf{5-clique:} $5$-\(Clique=\{\langle G \rangle | G \) is an undirected graph $G$ containing a clique on $5$ vertices $\}$.


{\em Solution: 



} 




\item \textbf{Small number partition:}
\( SNP = \{ \langle a_1, \dots, a_n \rangle | a_i \in \mathbb{N}$ and $\forall i,  a_i=1$ or $ a_i=2 $  and \(\exists S \subseteq \{1,..,n\} \Sigma_{i\in S} a_i = \Sigma_{j \notin S} a_j\}\) 



{\em Solution: 



} 





\end{enumerate}



\end{enumerate}
\end{document}
