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
