Problem $3,(30$ Pts$)$ We can think of a proof $($particularly in the context of computer science$)$ more generally as some evidence that proves a hypothesis. Now suppose there are two parties, Alice and Bob. Alice works at Property Testing Inc., where she is given an object $\backslash ($ X $\backslash )($in this case, a pair of labeled graphs $\backslash ($ G$\_\{1\},$ G$\_\{2\}\backslash ))$ and has to determine if the object has some property $\backslash ($ T $\backslash )($whether the graph $\backslash ($ G$\_\{1\}\backslash )$ is non$-$isomorphic to the graph $\backslash ($ G$\_\{2\}\backslash )).$

Bob also works at Property Testing Inc. and has developed a reputation over several years. Instead of testing properties using the standard property testing methods employed by the company, Bob simply guesses whether a given object has the property. Normally,

someone like that would get fired pretty quickly, but in Bob's case, he seems to always guess correctly. Bob insists that he doesn't just guess but has a way to generate a valid proof, though he has declined to share his proofs so far.

Alice has observed Bob for some time now and wants to get to the bottom of Bob's bag of tricks. She believes that if Bob can always generate a valid proof, there must be a systematic way for Bob to convince Alice of this without revealing his proof. So$,$ Alice comes up with the following game that she wants to play with Bob:

Alice is given two graphs, $\backslash ($ G$\_\{1\}\backslash )$ and $\backslash ($ G$\_\{2\}\backslash ),$ and needs to determine if they are non$-$isomorphic, meaning that no relabeling of vertices in $\backslash ($ G$\_\{1\}\backslash )$ will make it identical to $\backslash ($ G$\_\{2\}\backslash ).$ Bob claims he can prove that the two graphs are non$-$isomorphic without revealing any specific details about how he knows this.

To test Bob's claim, Alice devises the following protocol:

$1.$ Alice randomly chooses one of the two graphs, $\backslash ($ G$\_\{1\}\backslash )$ or $\backslash ($ G$\_\{2\}\backslash ),$ and gives Bob a randomly permuted version of that graph, $\backslash ($ G$^\{\backslash$prime$\}\backslash ),$ without revealing which graph she chose or how the vertices were relabeled.

$2.$ Alice then asks Bob to identify whether $\backslash ($ G$^\{\backslash$prime$\}\backslash )$ is the permuted version of $\backslash ($ G$\_\{1\}\backslash )$ or $\backslash ($ G$\_\{2\}\backslash ),$ effectively proving that he can distinguish between the two graphs.

$3.$ If Bob correctly identifies which graph $\backslash ($ G$^\{\backslash$prime$\}\backslash )$ corresponds to$,$ Alice can conclude that Bob knows the graphs are non$-$isomorphic. However, Bob must do this without revealing any details about the specific differences $($thus revealing a part of his secret proof$)$ between $\backslash ($ G$\_\{1\}\backslash )$ and $\backslash ($ G$\_\{2\}\backslash ).$

$4.$ Bob can convince Alice by consistently identifying the correct graph, thereby demonstrating that he knows the two graphs are non$-$isomorphic, even though Alice never sees the actual proof.

Alice repeats this process multiple times, each time randomly choosing one of the two graphs and permuting it$.$ If Bob can consistently identify the correct graph, Alice will be persuaded that the graphs $\backslash ($ G$\_\{1\}\backslash )$ and $\backslash ($ G$\_\{2\}\backslash )$ are indeed non$-$isomorphic. Can Bob successfully demonstrate that the two graphs $\backslash ($ G$\_\{1\}\backslash )$ and $\backslash ($ G$\_\{2\}\backslash )$ are non$-$isomorphic without revealing any specific details of his proof, using the above protocol?