\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}}

\newtheorem{objective}{Objective}

\begin{document}
  
  \begin{minipage}{\textwidth}
    CSE3502 - Theory of Computation \hfill \today\\
    \textbf{Not Due: Solutions will be posted next week}\\
    \\
    \centering{Homework 8} \hfill
  \end{minipage}

  \input{hw_survey}

  \section{Sanity Check} % (fold)
  \label{sec:sanity_check}
  
    Prove that every language in NP is decidable.
    \emph{(This is a test that you know the definitions)}
  
  % section sanity_check (end)

  \section{The Return of Graph Isomorphism} % (fold)
  \label{sec:the_return_of_graph_isomorphism}
  
    Recall the definition of graph isomorphism from homework 1.
    Prove that the following language is in NP.
    \[
      GRAPHISOMORPH = \{\rep{G,H} \mid  \text{$G$ and $H$ are isomorphic} \}
    \]
    Interestingly, this language is not known to be either in P or in NP-COMPLETE.
  
  % section the_return_of_graph_isomorphism (end)


  \section{Maybe we should bring back Roman Numerals.} % (fold)

    The Partition problem is defined as
    \[
      PARTITION = \left\{\rep{a_1,\ldots,a_k} \mid \text{there exists a subset $B\subset \{a_1,\ldots,a_k\}$ such that } 2\sum_{b\in B}b = \sum_{i=1}^k a_i \right\}
    \]

    Roman numerals use the alphabet $\{I,V,X,L,C,D,M\}$ to represent numbers, where
    \begin{align*}
      I &= 1\\
      V &= 5\\
      X &= 10\\
      L &= 50\\
      C &= 100\\
      D &= 500\\
      M &= 1000
    \end{align*}
    A number is represented as a string of these letters and the value of the number is the sum of the values of the symbols with some exceptions.
    If a symbol appears before a symbol of larger value, it is treated as negative.
    Thus, $IX= 9$, $XL = 40$, and $CM = 900$.
    There are some other rules, you may be familiar with, such as no symbol (other than $M$) can be repeated more than $3$ times in a row.
    So, $4$ must be written as $IV$ rather than $IIII$.
    Other than some isolated negative symbols, the string symbols are sorted in decreasing order of value.
    
    Now, $PARTITION$ is known to be NP-COMPLETE when numbers are written in binary.
    Prove that $PARTITION \in P$ if the input numbers are represented in Roman numerals.
    \emph{Hint: Use dynamic programming.}
    Is it really more efficient to work with Roman numerals?
    What's going on here?
  
  % section roman_numerals (end)

\end{document}