Interactive Protocols in Arthur-Merlin Games for Graph Nonisomorphism
Explore the concept of interactive protocols in Arthur-Merlin games for determining graph nonisomorphism. Arthur, a powerless knight, seeks to trust Merlin's advice but Merlin, all-powerful yet untrustworthy, must find ways to convince Arthur. Utilizing randomness, the games delve into graph isomorphism, NP complexity, and the challenge of determining subgraph isomorphism.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CMSC 281Complexity Theory Graph Nonisomorphism, Arthur-Merlin Protocols
Interactive Protocols Arthur-Merlin Games Arthur is a powerless knight. Merlin is all-powerful, but not trustworthy. How can Arthur become confident of Merlin s advice? Alternatively how can Merlin convince Arthur?
Interactive Protocols Arthur-Merlin Games Arthur is a powerless knight. Merlin is all-powerful, but not trustworthy. How can Arthur become confident of Merlin s advice? Alternatively how can Merlin convince Arthur? Use randomness.
Interactive Protocols Arthur-Merlin Games Arthur is a powerless knight. Merlin is all-powerful, but not trustworthy. How can Arthur become confident of Merlin s advice? Alternatively how can Merlin convince Arthur? Use randomness. Graph non-isomorphism: G1, G2are isomorphic if there is a 1-1 onto mapping f of the vertices of G1to the vertices of G2that preserves adjacency. [(u,v) is an edge of G1iff (f(u), f(v)) is an edge of G2]
Interactive Protocols Arthur-Merlin Games Arthur is a powerless knight. Merlin is all-powerful, but not trustworthy. How can Arthur become confident of Merlin s advice? Alternatively how can Merlin convince Arthur? Use randomness. Graph non-isomorphism: G1, G2are isomorphic if there is a 1-1 onto mapping f of the vertices of G1to the vertices of G2that preserves adjacency. [(u,v) is an edge of G1iff (f(u), f(v)) is an edge of G2] It is clear that graph isomorphism is in NP (but likely not NP-complete)
Interactive Protocols Arthur-Merlin Games Arthur is a powerless knight. Merlin is all-powerful, but not trustworthy. How can Arthur become confident of Merlin s advice? Alternatively how can Merlin convince Arthur? Use randomness. Graph non-isomorphism: G1, G2are isomorphic if there is a 1-1 onto mapping f of the vertices of G1to the vertices of G2that preserves adjacency. [(u,v) is an edge of G1iff (f(u), f(v)) is an edge of G2] It is clear that graph isomorphism is in NP (but likely not NP-complete) [Exercise: the problem Does G2 have a subgraph isomorphic to G1is NP-complete]
Interactive Protocols Arthur-Merlin Games Arthur is a powerless knight. Merlin is all-powerful, but not trustworthy. How can Arthur become confident of Merlin s advice? Alternatively how can Merlin convince Arthur? Use randomness. Graph non-isomorphism: G1, G2are isomorphic if there is a 1-1 onto mapping f of the vertices of G1to the vertices of G2that preserves adjacency. [(u,v) is an edge of G1iff (f(u), f(v)) is an edge of G2] It is clear that graph isomorphism is in NP (but likely not NP-complete) Not known whether G1not isomorphic to G2 is in NP.
Interactive Protocols Arthur-Merlin Games Arthur is a powerless knight. Merlin is all-powerful, but not trustworthy. How can Arthur become confident of Merlin s advice? Alternatively how can Merlin convince Arthur? Use randomness. Merlin claims to be able to prove n-vertex graphs G1, G2nonisomorphic. 1 step of Arthur s strategy: Use randomness to generate a random permutation ? of [1..n] Use randomness to choose i to be 1 or 2. Apply ? to Giobtaining graph H Ask Merlin which of G1, G2H is isomorphic to.
Analysis of the Protocol Use randomness. Merlin claims to be able to prove n-vertex graphs G1, G2nonisomorphic. 1 step of Arthur s strategy to verify Merlin s claim: Use randomness to generate a random permutation ? of [1..n] Use randomness to choose i to be 1 or 2. Apply ? to Giobtaining graph H Ask Merlin which of G1, G2H is isomorphic to. If Merlin gives the wrong answer, we re done. If Merlin gives the correct answer, but G1, G2are isomorphic, note that Merlin has only probability of .5 to be right. Repeat the protocol (with new random choices) k times. Chances that Merlin can get lucky every time is 2-k.
Formalization IP is the set of protocols of polynomial size, with BPP-like correctness guarantees. We do not have time to make all of this formal. It can be done (section 10.4)
Formalization IP is the set of protocols of polynomial size, with BPP-like correctness guarantees. We do not have time to make all of this formal. It can be done (section 10.4) The model is conceptually important: NP feasible proofs IP feasible probabilistic interactions
Formalization IP is the set of protocols of polynomial size, with BPP-like correctness guarantees. We do not have time to make all of this formal. It can be done (section 10.4) The model is conceptually important: NP feasible proofs IP feasible probabilistic interactions Theorem: IP=PSPACE
Formalization IP is the set of protocols of polynomial size, with BPP-like correctness guarantees. We do not have time to make all of this formal. It can be done (section 10.4) The model is conceptually important: NP feasible proofs IP feasible probabilistic interactions Theorem: IP=PSPACE The techniques of the proof turn out to be important .
