%You can leave alone everything before Line 84.
\def\draft{1}

\documentclass{article}
\usepackage{url,amsfonts, amsmath, amssymb, amsthm, color}
% Page layout
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\parindent}{1pc}
\newcommand{\shortbar}{\begin{center}\rule{5ex}{0.1pt}\end{center}}
%\renewcommand{\baselinestretch}{1.1}
% Macros for course info
\newcommand{\courseNumber}{CMSC 652}
\newcommand{\courseTitle}{Complexity Theory}
\newcommand{\semester}{Fall 2017}
% Theorem-like structures are numbered within SECTION units
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{statement}[theorem]{Statement}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}{Fact}
%definition style
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}{Example}
%\newtheorem{problem}{Problem}
\newtheorem{exercise}{Exercise}
\newtheorem{algorithm}{Algorithm}
%remark style
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{reduction}[theorem]{Reduction}
%\newtheorem{question}[theorem]{Question}
\newtheorem{question}{Question}
%\newtheorem{claim}[theorem]{Claim}
%
% Proof-making commands and environments
\newcommand{\beginproof}{\medskip\noindent{\bf Proof.~}}
\newcommand{\beginproofof}[1]{\medskip\noindent{\bf Proof of #1.~}}
\newcommand{\finishproof}{\hspace{0.2ex}\rule{1ex}{1ex}}
\newenvironment{problem}[1]{\medskip\noindent{\bf Problem #1.~}}{\shortbar}
\newenvironment{solution}[1]{\medskip\noindent{\bf Solution #1.~}}{\shortbar}

\ifnum\draft=1
\newcommand{\note}[1]{{\color{blue} #1}}
\newcommand{\cmt}[1]{{\color{red} #1}} 
\else
\newcommand{\note}[1]{{}}
\newcommand{\cmt}[1]{{#1}} 
\fi


%====header======
\newcommand{\solutions}[3]{
%\renewcommand{\thesolution}{{\large #2}.\arabic{problem}}
\vspace{-2ex}
\begin{center}
{\small  \courseNumber, \courseTitle
\hfill {\large \bf {Due: #1} }\\
\semester, University of Maryland \hfill
{\em Date: #3}}\\
\vspace{-1ex}
\hrulefill\\
\vspace{4ex}
{\Large #2}\\
\vspace{2ex}
\end{center}
\shortbar
\vspace{3ex}
}

\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\solutions{September 12th, 2017}{Assignment 1}{\today}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Begin the solution for each problem by
% \begin{solution}{Problem Number} and ends it with \end{solution}
%
% the solution for Problem 1

\textbf{You must submit it electronically to ELMS}. This is a group assignment. Every group only needs to submit one solution. Group members get the same credit for the group submission. 

This assignment is 7\% in your total points. For the simplicity of the grading, the total points for the assignment is 70. 

\begin{problem}{1 [10 pts]} Let $T(\cdot)$ be an increasing computable function. Show that there exists a decidable language $A$ such that the following occurs: 

If $M$ is a TM that, on all inputs of length $n$, halts in $\leq T(n)$ time, then there is an INFINITE NUMBER of $x$ such that $A(x)\neq M(x)$. (Here we let $A(x)=1$ if $x \in A$ otherwise $A(x)=0$.) 
\end{problem}

\begin{problem}{2 [10 pts]} 
Assume $L_1, L_2 \in$ NP and $S_1\in$ CoNP. Assume NP$\neq$CoNP.  Answer each of the following with proof or a counter-example. 

\begin{itemize}
 \item[(a)] Is $L_1 \cup L_2$ necessarily in NP?
 \item[(b)] Is $L_1 \cup S_1$ necessarily in CoNP?
\end{itemize}
\end{problem}

\begin{problem}{3 [15 pts]}
Assume that the decision problem of Graph Isomorphism is in P. Show that the following function
can be computed in poly-time.  Given two graphs $G_1,G_2$, 
\begin{itemize}
\item If $G_1$ and $G_2$ are not isomorphic than output NO.
\item If $G_1$ and $G_2$ are isomorphic than output an isomorphism.
\end{itemize}
(Hint: please be careful! an intuitive approach might not work!) 
\end{problem}

\begin{problem}{4 [15 pts]}
Prove that the following language 
\[
L= \{ (M, x, 1^t): \exists w \in \{0,1\}^t, s.t., M(x, w) \text{ halts within } t \text{ steps with output 1} \}
\]
(where $M$ is a deterministic Turing machine) is NP-complete. 
\end{problem}

\begin{problem}{5 [20 pts]}
Prove that the following language is NP-complete
\[
   \mathrm{3COL}=\{ G : \text{there exists a coloring of } G \text{ with 3 colors s.t. no adjacent vertices share the same color.} \}
\]
(Hint: You can assume 3SAT is NP-complete. You may use other resources but let me know what they are and you should hand in your own solution.)
\end{problem}

\end{document}
