## [Computational Complexity] What is the probability that ...

Expand Messages
• (I ve been on vacation for the last 10 days on a Tauck Bus Tour of Canada with Heli-hiking.) What is the probability that a bus tour has on it two people that
Message 1 of 1 , Aug 11, 2008
• 0 Attachment
(I've been on vacation for the last 10 days on a Tauck Bus Tour of Canada with Heli-hiking.)

What is the probability that a bus tour has on it two people that know the proof that S2S is decidable? (Original Proof by Rabin is here. For reviews of several books on the topic see here.)
1. Not a trick question. The bus tour was not organized by the Association of Symbolic Logic.
2. The prob seems like it would be low. But this is not the right way to look at it.
3. This did happen. Suzanne Zeitman was on the tour. I learned about the proof from her (excellent) writeup which, alas, is not online. It is incorporated in the book The Classical Decision Problem by Borger, Gradel, Gurevich.
4. Should I be saying `WOW! that is so unlikely, yet it happend!'. No. Consider the following fictional conversation:

BILL: The most amazing thing just happened! I just tossed a coin 40 times and got HHTTTHTHTHTHHTTTTHTHTHTTHTHHHTTHHTHTHHTH.

LANCE: Why is that remarkable?

BILL: Because the prob of that particular sequence is so small!
5. The prob that someone the distance away from me which Suzanne Zeitman is (I have written some math reviews for her and been in some email contact) happens to be on the same bus trip as me may be low, but its not so low as to be astonished if it happens. This is my third bus trip and the first time it happened. Is the probably 1/3? I doubt that, but its not so low as to be notable.
6. If before going on the trip I had said Gee, I wonder is someone who knows the proof that S2S is decidable will be on the tour? then THAT Would be notable.
7. What is the prob that the maintainer of the Erdos-Number Website was, Jerry Grossman, was on the trip? This is a trick question-- Jerry Grossman is Suzanne Zeitman's husband.
8. What is the prob that on the trip there were people who know, through their homeowners association, Steven Simpson an eminent logician who works on Reverse Mathematics, who I know. This did happen. Not a trick question, but again, not that notable.

--
Posted By GASARCH to Computational Complexity at 8/11/2008 11:30:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.