h10_ajkofink.tex

\documentclass[11pt, oneside]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{gensymb}
\usepackage{geometry}
\geometry{letterpaper}
\usepackage{tikz}
\usepackage{graphicx}
\usepackage{siunitx}
\usepackage{upgreek}
\usepackage{qtree}

\title{h10-ajkofink\\CSC 333 (001)}
\author{Andrew Kofink}
\date{23 April 2014}

\begin{document}
\maketitle

\begin{enumerate}
  \item Since NP is a superset of NPC and P, assume M1SAT $\in$ NP. In order to
    prove that M1SAT $\in$ NPC, we must show that $M1SAT \leq_p X \wedge
    X \leq_p M1SAT$ where X $\in$ NPC. In order to show this, we must devise a
    transform function for M1SAT which runs in P time. For this problem, it is
    easy to check the 3SAT problem in time P for a given set of variables A.
    This condition must hold, and the number of non-negated terms, $x_i$, in the
    solution clause must be $\leq k$.
  \item
  \item
  \item
  \item
  \item
\end{enumerate}

\end{document}