\documentclass{article}
\usepackage{amsmath,amssymb,amsthm,latexsym,paralist}

\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem*{solution}{Solution}
\newtheorem*{resources}{Resources}

\newcommand{\name}[1]{\noindent\textbf{Name: #1}}
\newcommand{\honor}{\noindent On my honor, as an Aggie, I have neither
  given nor received any unauthorized aid on any portion of the
  academic work included in this assignment. Furthermore, I have
  disclosed all resources (people, books, web sites, etc.) that have
  been used to prepare this homework. \\[1ex]
 \textbf{Signature:} \underline{\hspace*{5cm}} }
 
\newcommand{\checklist}{\noindent\textbf{Checklist:}
\begin{compactitem}[$\Box$] 
\item Did you add your name? 
\item Did you disclose all resources that you have used? \\
(This includes all people, books, websites, etc. that you have consulted)
\item Did you sign that you followed the Aggie honor code? 
\item Did you solve all problems? 
\item Did you submit the pdf file resulting from your latex file 
  of your homework?
\item Did you submit a hardcopy of the pdf file in class? 
\end{compactitem}
}

\newcommand{\problemset}[1]{\begin{center}\textbf{Problem Set #1}\end{center}}
\newcommand{\duedate}[2]{\begin{quote}\textbf{Due dates:} Electronic
    submission of this homework is due on \textbf{#1} on ecampus, a
    signed paper copy of the pdf file is due on \textbf{#2} at the
    beginning of class. \end{quote} }

\newcommand{\N}{\mathbf{N}}
\newcommand{\R}{\mathbf{R}}
\newcommand{\Z}{\mathbf{Z}}


\begin{document}
\problemset{8}
\duedate{4/18/2019 before 12:30pm}{4/18/2019}
\name{ (put your name here)}
\begin{resources} (All people, books, articles, web pages, etc. that
  have been consulted when producing your answers to this homework)
\end{resources}
\honor

\newpage

Read Chapter 34 in our textbook. 

\begin{problem} (20 points) % 
A boolean formula is said to be in disjunctive normal form if and only
if it is the disjunction of clauses, where each clause is the
conjunction of literals (e.g. $(x \wedge \neg y\wedge \neg z) \vee (\neg
x \wedge \neg y \wedge z)$ is in disjunctive normal form). 
Show that there exists a polynomial-time algorithm to determine
whether a boolean formula in disjunctive normal form is satisfiable. 
\end{problem}
\begin{solution}
\end{solution}

\begin{problem} (20 Point) 
Dr. S.M. Art Aleck thinks he deserves the Turing award as he gave the
following compelling argument that SAT can be solved in polynomial
time. Given a boolean formula $f$ in conjuctive normal form, simply
convert $f$ to disjunctive normal form and use the poly-time algorithm
from the previous problem to determine whether $f$ is
satisfiable. Explain why Dr. Aleck is mistaken. 
\end{problem}
\begin{solution}
\end{solution}

\begin{problem} (20 points) 
Consider the language 
$$\text{GRAPH-ISOMORPHISM} = \{ (G_1, G_2) : G_1 \text{
  and } G_2 \text{ are isomorphic
graphs}\}.$$ Prove that GRAPH-ISOMORPHISM is in NP by describing a
polynomial-time algorithm to verify the language. 
\end{problem}
\begin{solution}
\end{solution}


\begin{problem} (20 points) % If NP != co-NP then NP != P. 
Exercise 34.2-10 on page 1066. [Hint: Read Chapter 34.2 and make sure you
understand the definition of co-NP.]  
\end{problem}

\begin{problem} (20 points) % Set partition is NP complete
Exercise 34.5-5 on page 1101 [Hint: Reduce SUBSET SUM
to SET PARTITION.] 
\end{problem}

Make sure that you write the solutions in your own words!
\medskip



\goodbreak
\checklist
\end{document}
