There are two lessons I’d like to draw from Rudich’s Fable of the Chessmaster. The reason was discovered in 1990 by Lund, Fortnow, Karloff, Nisan, and Shamir, and has less to do with chess than with the zeroes of polynomials over finite fields. By asking a short sequence of randomly-chosen questions, each a followup to the last, the crowd can quickly convince itself, to as high a confidence as it likes, that the man they’re interrogating knows a winning strategy for White - or else expose his lie if he doesn’t. Most of you know the punchline to this story, but for those who don’t: the nerd is wrong. So unless you’re prepared to grant us immortality, there’s no way you can possibly convince us!” We’ll be long dead before every possibility is examined. “But there are more sequences of moves than there are atoms in the universe! Even supposing you beat us every day for a century, we’d still have no idea whether some sequence of moves we hadn’t tried yet would lead to your defeat. “O ye of little faith! As long as I play White, it’s not just hard to beat me - it’s mathematically impossible! Play Black over and over, try every possible sequence of moves, and you’ll see: I always win.”Ī nerd pipes up. ![]() “But that still doesn’t mean you’re God.” “OK, so you’re pretty good at chess,” the onlookers concede. “Well,” says the man,”I can beat anyone at chess.”Ī game is duly arranged against Kasparov, who happens to be in town. If a layperson asks you what computational complexity is, you could do worse than to tell the following story, which I learned from Steven Rudich.Ī man with a flowing gray beard is standing on a street corner, claiming to be God.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |