Lesson 4

A similar trick for graph non-isomorphism looks like this. Suppose someone wrote a program that, given any two graphs, tells whether they are isomorphic or not. As we discussed above, if the graphs are isomorphic, the program can quickly provide the isomorphism itself. However, if no isomorphism exists, it is unclear what could be considered a (short) proof of this. But you can verify the correctness of the program in an interactive mode as follows. Suppose the program said that two graphs \(G_{0}\) and \(G_{1}\) are non-isomorphic. Then repeat the following \(k\) times. Choose a random graph \(G \in \{G_{0}, G_{1}\}\), then choose a random permutation \(\sigma \in S_{n}\) and ask the program whether the graphs \(G_{0}\) and \(\sigma(G)\) are isomorphic. If \(G_{0}\) and \(G_{1}\) are non-isomorphic, we expect a specific answer from the program: “isomorphic” if \(G=G_{0}\), and “non-isomorphic” if \(G=G_{1}\). If the program's answer is not as expected, we conclude that it is incorrect. If the graphs \(G_{0}\) and \(G_{1}\) are isomorphic, then with a probability of \(1/2\), the answer will not be what we expect, as the graph \(\sigma(G)\) could equally likely come from \(G_{0}\) or \(G_{1}\). Therefore, after \(k\) repetitions, the probability of not catching an incorrect program will be only \(1/2^{k}\).

Interactive proofs were introduced in 1985 by László Babai and independently by Shafi Goldwasser, Silvio Micali, and Charles Rackoff. In 1990, Adi Shamir proved that short interactive proofs exist for all problems solvable with polynomial space, i.e., that IP\(=\)PSPACE. (The class PSPACE is huge: any reasonable computational problem that comes to your mind most likely lies within it.)