# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1415415094 0
# Node ID 81a08931ecb41d4d60141119ff9624cb25e9b7a3
# Parent  5e8ffb58bdaa7201dc7ec60e48b20caa50848f39
updated

diff -r 5e8ffb58bdaa -r 81a08931ecb4 handouts/ho06.pdf
Binary file handouts/ho06.pdf has changed
diff -r 5e8ffb58bdaa -r 81a08931ecb4 handouts/ho06.tex
--- a/handouts/ho06.tex	Sat Nov 08 02:28:30 2014 +0000
+++ b/handouts/ho06.tex	Sat Nov 08 02:51:34 2014 +0000
@@ -203,7 +203,51 @@
 problem at hand.\footnote{The question whether $P = NP$ or not,
 we leave to others to speculate about.} 
 
-One NP problem is the \emph{graph isomorphism problem}.
+One NP problem is the \emph{graph isomorphism problem}. It
+essentially determines whether the following two graphs, say
+$G_1$ and $G_2$, can be moved and stretched so that they look
+exactly the same.
+
+\begin{center}
+\begin{tabular}{c@{\hspace{8mm}}c@{\hspace{8mm}}c}
+$G_1$ & $G_2$\\
+\raisebox{-13mm}{\includegraphics[scale=0.4]{../pics/simple.png}} &
+\raisebox{-13mm}{\includegraphics[scale=0.4]{../pics/simple-b.png}}&
+
+\footnotesize
+\begin{tabular}{rl}
+Graph $G_1$	& Graph $G_2$\\
+a	& 1\\
+b	& 6\\
+c	& 8\\
+d	& 3\\
+g	& 5\\
+h	& 2\\
+i  &  4\\
+j  & 7\\
+\end{tabular}
+\end{tabular}
+\end{center}
+
+\noindent The table on the right gives a mapping of the nodes
+of the first graph to the nodes of the second. With this we
+can check: node $a$ is connected in $G_1$ with $g$, $h$ and
+$i$. Node $a$ maps to node $1$ in $G_2$, which is connected to
+$2$, $4$ and $5$, which again correspond via the mapping. Let
+us write $\sigma$ for such a table and let us write
+
+\[G_1 = \sigma(G_2)\]
+
+\noindent for two isomorphic graphs. It is actually very 
+easy to construct two isomorphic graphs: Start with an
+arbitrary graph, re-label the nodes consistently. What
+Alice need for the protocol below is to generate such 
+isomorphic graphs.
+
+Now the secret which Alice tries to hide is the knowledge of
+such an isomorphism $\sigma$ between two such graphs. But she
+can convince Bob whether she knows such an isomorphism for two
+graphs. 
 
 \subsubsection*{Using Modular Arithmetic for ZKP Protocols}