[Cs5500] QUESTION REGARDING PROTOCOL FOR RL_BFS PLAYGROUND

[Sandeep Upendra Kamath]

Dear Sir,

When you introduced the RL_BFS playground in the class you suggested using
"ForAllExists" protocol.
But while discussing among ourselves we found this game not exactly
following the above protocol.

Heres our understanding of the game and it following  "ForAllExists"
protocol:

 -- ALICE :

CLAIM: Alice makes a generic claim making a statement that  "n-node
undirected graph G=(V,E)
contains two nodes s and t such that the distance between s and t is
strictly
greater than n/2. And there exists some node v,not equal to either
s or t, and deleting v from G destroys all s-t paths."

 -- BOB: bob can do either of the following:

(1) AGREES: if bob agrees (BOOLEAN = true),the agreement protocol is
executed

(2) REFUTES: if bob refutes the claim (BOOLEAN = false)then he provides an
instance x= (G,s,t) for which he believes there is no "v".

 -- ALICE:

Alice now to defend herself solves the instance (G,s,t) by providing a "v"
which on its removal disconnects "s" and "t".

But our question about the above implementation is as follows

(i) In the MMG domain cliam made was a value c, here the claim is just a
generic statement. What would the propose function return.

(ii) How would the agreement protocol work in this case.

(iii) We had a general question about the domain. Is claim  being made in
this domain always true in the world of graphs.

kindly guide us further.

Regards,
Sandeep Kamath
Team Navi
-------------- next part --------------
HTML attachment scrubbed and removed