We consider the graph isomorphism problem: Given two graphs G_1 and G_2, are they isomorphic? If you solve this problem and find that the two graphs are indeed isomorphic, it is very easy for you to convince me of this fact: We assume that |G_1|=|G_2|=n (since if they have different numbers of vertices, they clearly cannot be isomorphic). For me to believe you, you can simply find an element \pi\in S_n that induces an isomorphism of the two graphs.

What if they aren’t isomorphic? You could try to find an invariant that differs. But that’s a rather ad hoc technique, and maybe you aren’t able to find one, but you still know that the two graphs are nonisomorphic (somehow). We can play a game that will help you convince me that the two graphs are nonisomorphic. I create a list of (say) 50 numbers a_1,a_2,\ldots,a_{50}, with each a_i=1,2. Then I randomly choose permutations \pi_i\in S_n and construct the graphs \pi_i G_{a_i} and give you this list. Now you have to tell me whether each a_i is equal to 1 or 2. If the the two graphs are isomorphic, you’ll only get the graphs right half the time (since you’re just guessing in this case), so it’s very unlikely that you’ll always get it right. However, if they’re nonisomorphic, then you can (somehow) figure out which graphs on my list are isomorphic to G_1 and which to G_2 and get them all right.

The class of problems (such as the graph nonisomorphism problem) that can be solved with this sort of interaction is called the Arthur Merlin (or AM) complexity class.