[Cs4800] HW3 question

[Karl Lieberherr]

Hi Andrei and Ken:

by inverse you mean negation.

Let's see whether this helps:

Alice claims:
Exists C ForAll G: f(G)<=C

Refutation:
Alice gives C0
Bob gives G0: f(G0) > C0
Expl: Bob wins because he found a G0 that contradicts Alice claim.

Bob claims:
ForAll C Exists G: f(G) > C

Refutation:
Alice gives C0
Bob gives G0: f(G0) < C0
Expl: Alice wins because Bob did not find what he claimed.

What is confusing: If Alice claims:
ForAll C Exists G: f(G) > C
then the roles of Alice and Bob would have to be reversed.
I think you used those reversed roles. But Bob must make the negated claim.
He is in a good position to make this claim because he
successfully refuted Alice claim.

You were thinking in terms of Alice making the negated claim.

I agree with Ken that the claim on page 110 is false.
But we need an algorithm that constructs the graphs defending the
negated claim.

-- Karl


On Fri, Sep 24, 2010 at 3:10 PM, <andrei at ccs.neu.edu> wrote:

> 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
>
>
> _______________________________________________
> Cs4800 mailing list
> Cs4800 at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/cs4800
>
-------------- next part --------------
HTML attachment scrubbed and removed