[Cs4800] HW3 question

[andrei at ccs.neu.edu]

Hi Ken,

Thanks for the response. I see what you're saying, but I think playing through the games isn't enough to definitively prove the claim one way or the other. For example, if Bob refutes Alice in the first game, the only thing that can be definitely stated is that the 'c' Alice chose isn't the one she claims exists to satisfy the predicate for all graphs.

The difficulty I'm having is in the imbalance of the games. So far Aaron and I have found that it takes a lot of effort in terms of picking a graph for Bob to refute Alice (if a c > 3 is chosen), but it seems trivial for Alice to refute Bob's inverse claim using the inverse game described in my earlier e-mail.

If it's easy for Alice to refute Bob, but difficult for Bob to refute Alice, to me that suggests that Alice's claim is more likely true - which goes against the intuition you have (and I share) about the problem. That's why I think there might be something wrong with the way I am formulating the inverse game.

Andrei

----- Original Message -----
From: "Kenneth K Sham" <sham.k at husky.neu.edu>
To: "Andrei Mackenzie" <andrei at ccs.neu.edu>
Sent: Friday, September 24, 2010 2:41:36 PM GMT -05:00 US/Canada Eastern
Subject: Re: [Cs4800] HW3 question

Hi Andrei, 
I don't think your question makes sense. Either the original claim is true or the negation is true. If the original claim is true, then the negation is never true; ergo, there's no way for someone to refute the claim. And if the negation is true, then it's impossible to refute it. 

So just from my thoughts (I haven't played the games yet), I believe the claim on page 110 is false. You can always construct a graph (given c) such that the diam(G)/apd(G) > c. Since there is no limit placed on the graph G(V,E), it's impossible to find a value c that limits G in diam(G)/apd(G). 

Hope that helps, 
Ken 



On Fri, Sep 24, 2010 at 1:18 PM, Andrei Mackenzie < andrei at ccs.neu.edu > wrote: 


Hello all, 

Aaron and I are still confused about the inverse of the game for problem 1. In the first game (Alice challenges Bob), Bob tries to find an instance of a graph for which the inverse of the predicate in Alice's claim holds. In the second game, Bob makes the inverse of Alice's claim, and we agreed that Bob must select a c and challenge Alice to produce a G. If I understand correctly, the G that Alice produces must satisfy the inverse of Bob's claim, i.e. it must satisfy Alice's original claim from the first game. 

This seems trivially easy for Alice to do with the particular predicate in the problem - I can think of the same graph that would do it regardless of the c that Bob chooses. Did I misunderstand something? 

Thanks for your help! 

Andrei 

_______________________________________________ 
Cs4800 mailing list 
Cs4800 at lists.ccs.neu.edu 
https://lists.ccs.neu.edu/bin/listinfo/cs4800