\documentclass{article}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{fullpage}
\usepackage{eucal}
\usepackage{graphicx}
\usepackage{color}
\usepackage{tikz}
\usepackage{algorithm,algorithmic}

\newcommand{\e}{\varepsilon}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\question}[1]{\vspace{10pt}\noindent $\mathbf{#1}$}
\newcommand{\yieldstar}{\stackrel{*}{\Rightarrow}}
\newcommand{\yields}{\Rightarrow}
\newcommand{\blank}{\text{\textvisiblespace}}
\newcommand{\rep}[1]{\langle #1 \rangle}
\newcommand{\TIME}{\text{\textsc{Time}}}
\newcommand{\Ozgur}{\text{\textsc{Ozgur}}}
\newcommand{\tab}{\hspace{30pt}}
\newcommand{\NPC}{\textsc{NP-Complete}}

\newtheorem{objective}{Objective}

\begin{document}
  
  \begin{minipage}{\textwidth}
    CSE3502 - Theory of Computation \hfill \today\\
    \textbf{Due: Before class on April 29, 2014}\\
    \\
    \centering{Homework 9} \hfill
  \end{minipage}

  \input{hw_survey}

  \section{Reductions and NP-Completeness} % (fold)

    Let $A$ and $B$ be languages such that $A\le_P B$.
    That is, there is a polylnomial-time reduction from $A$ to $B$.
    In each question below there are some suppositions about $A$ and $B$ followed by some possible conclusions.
    Circle all of the possible conclusions that are \emph{necessarily} true assuming the suppositions.    

    \question{1.1}\\
    \textbf{Suppose:} $A\in P$ and $B\in \NPC$.\\ 
    \textbf{Conclude:} $A\in NP$?  $A\in \NPC$?
    
    \question{1.2}\\
    \textbf{Suppose:} $A\in \NPC$ and $B\in P$.\\ 
    \textbf{Conclude:} $B\in NP$?  $B\in \NPC$? $A\in P?$

    \question{1.3}\\
    \textbf{Suppose:} $A\in NP$ and $B\in P$.\\ 
    \textbf{Conclude:} $B\in \NPC$? $A\in P$?  $P = NP$?

    \question{1.4}\\
    \textbf{Suppose:} $A\in \NPC$.\\ 
    \textbf{Conclude:} $B\in \NPC$?
    
  % section reductions (end)

  \section{Subgraph Isomorphism} % (fold)
  \label{sec:subgraph_isomorphism}
    
    \question{2.1}
    The \emph{clique} problem takes as input a graph $G$ and a number $k$, and it asks whether or not $G$ has a clique (a complete subgraph) of size $k$.  The Sipser book contains a proof that the clique problem is \NPC.
  
    The \emph{subgraph isomorphism} problem takes as input a pair of graphs and asks if the first graph is isomorphic to a subgraph of the second graph.  Prove that subgraph isomorphism is \NPC.
  
    \question{}
    \textbf{To think about:} Why doesn't your answer work to show also that graph isomorphism is \NPC?
  
  % section subgraph_isomorphism (end)


\end{document}