Heh...
Funny web comic touching on complexity theory.
From Request Comics. Handed across the room by Madhu to Brendan, who showed it to me.
Earlier I'd seen another, slightly more reverent, comics treatment of Interactive Proofs, by Larry Gonick of 'Cartoon History of the Universe' fame.
To briefly discuss the Request Comics scenario: suppose an alien claims to play perfect chess (in all positions) on an n-by-n board; is it possible to efficiently test this in a poly(n)-length randomized interaction?
If there's only one alien, this might be too hard, since the 'correct' generalization of Chess is EXPTIME-complete. If we instead play a PSPACE-complete game like Hex (or Chess with a truncated game length of poly(n)), things change: Shamir's Theorem tells us how a Verifier can be convinced that any particular board set-up is a win.
But this is not the same as Prover convincing Verifier that Prover plays perfectly! However, additional ideas can help. Feigenbaum and Fortnow showed that every PSPACE-complete language L has a worst-case-to-average case reduction to some sampleable distribution D on instances.
This means there exists a randomized algorithm A^B using a black-box subroutine B, such that for all problem instances x, and for all possible black-boxes B that correctly answer queries of form 'is y in L?' with high probability when y is drawn according to distribution D,
A^B(x) accepts with high prob. if x is in L, and rejects w.h.p. if x is not in L.
Thus for the Prover to convince Verifier that Prover is 'effectively able' to solve L in the worst case (and L may encode how to play perfect Hex), it's enough to prove that Prover can decide L w.h.p. over D. Since D is sampleable, Verifier may draw a sample y from D, and the two can run an interactive proof for L on it (or L-complement, if Prover claims y isn't in L). Repeat to increase soundness.
From Request Comics. Handed across the room by Madhu to Brendan, who showed it to me.
Earlier I'd seen another, slightly more reverent, comics treatment of Interactive Proofs, by Larry Gonick of 'Cartoon History of the Universe' fame.
To briefly discuss the Request Comics scenario: suppose an alien claims to play perfect chess (in all positions) on an n-by-n board; is it possible to efficiently test this in a poly(n)-length randomized interaction?
If there's only one alien, this might be too hard, since the 'correct' generalization of Chess is EXPTIME-complete. If we instead play a PSPACE-complete game like Hex (or Chess with a truncated game length of poly(n)), things change: Shamir's Theorem tells us how a Verifier can be convinced that any particular board set-up is a win.
But this is not the same as Prover convincing Verifier that Prover plays perfectly! However, additional ideas can help. Feigenbaum and Fortnow showed that every PSPACE-complete language L has a worst-case-to-average case reduction to some sampleable distribution D on instances.
This means there exists a randomized algorithm A^B using a black-box subroutine B, such that for all problem instances x, and for all possible black-boxes B that correctly answer queries of form 'is y in L?' with high probability when y is drawn according to distribution D,
A^B(x) accepts with high prob. if x is in L, and rejects w.h.p. if x is not in L.
Thus for the Prover to convince Verifier that Prover is 'effectively able' to solve L in the worst case (and L may encode how to play perfect Hex), it's enough to prove that Prover can decide L w.h.p. over D. Since D is sampleable, Verifier may draw a sample y from D, and the two can run an interactive proof for L on it (or L-complement, if Prover claims y isn't in L). Repeat to increase soundness.
Labels: complexity
posted by Andy D at
5:50 PM
8 Comments:
Wouldn't an easier approach be the following:
- Prove that the initial board is a win for white (say). Assume the prover plays black (things are even easier if the prover plays white).
- During the course of the game, after every move by the opponent (white), the prover does one of two things:
-- either proves that the current board is still a win for white
-- or else proposes a move for black and proves that this gives a board which is a win for black.
By
Anonymous, at 4:31 AM
anon--for general games, at least, this protocol fails to be convincing; it runs into the same problem pointed out by the comic of how to convince a Verifier who happens to a crappy player.
For example: consider a game having the following form: Say white is played by Verifier as you say, and the game has the following form:
-White's first move does nothing.
-Black then makes a move consisting of a choice between the 'easy way' and the 'hard way': two subgames. The two players then play the chosen subgame to determine the winner.
The two subgames are designed so as each to be game-theoretically wins for White; however, the 'easy way' game is trivial, while the 'hard way' game is, well, hard.
Running your protocol, after White's first (null) move, Black (Prover) proves the board is still a win for white. Then, your protocol seems to allow Black free choice of the next move, so Black chooses the easy way, and the rest of the protocol is a triviality.
Black has failed to convince White that Black knows a way for White to fight through the 'hard way', which any perfect strategy for White must contain (since Black can choose to go that way).
By
Anonymous, at 5:24 PM
This comment has been removed by a blog administrator.
By
M-Wave, at 9:24 AM
In the original Karp-Lipton advice paper we studied a related question. Suppose that you have a set of players--one who is perfect--and a chess position. Whose advice do you use?
By
dick lipton, at 11:30 PM
God this sounds like my biology test of the last week :S
Thanks for sharing.
By
viagra online, at 9:09 AM
I would like to visit this site because I love the American comics, I have never known about this web comic
By
xlpharmacy, at 10:36 AM
this article is very good!
By
Louis Vuitton Outlet, at 3:56 AM
Hey! Coach Factory Online simply wanted to say your website is one of the nicely laid out, most inspirational I have come across in quite a while.
By
Coach Factory Online, at 2:45 AM
Post a Comment
<< Home