Lesson 1

Let graphs \(G_{0}\) and \(G_{1}\) be non-isomorphic. Now we will construct a proof that, on one hand, will be very long, but on the other hand, you will only need to read a constant number of bits from it to verify its correctness. The proof will be a bit string of length \(2^{\binom n2}\), indexed by all graphs on \(n\) vertices. In the cell corresponding to graph \(H\), we will write \(i \in \{0,1\}\) if \(H\) is isomorphic to \(G_{i}\), and anything otherwise.

To give an example, consider these two graphs.

How do we check such a proof? We choose a random graph \(G \in \{G_{0}, G_{1}\}\), then choose a random permutation \(\sigma \in S_{n}\) and read the bit of the proof from the cell \(\sigma(G)\). If the graphs are non-isomorphic, then it should contain the number \(i\). Accordingly, if we see something other than \(i\) there, we reject this proof. On the other hand, if \(G_{0}, G_{1}\) were isomorphic, then \(\sigma(G)\) could equally likely come from \(G_{0}\) or \(G_{1}\). And whatever is written in the cell \(\sigma(G)\), we will reject it with a probability of \(1/2\). Repeating this \(k\) times, we reduce the error probability to \(1/2^{k}\).