Ask Bob
A new game that helps us understand the structure of 
Dieter van Melkebeek is a theorist at the University of Wisconsin at Madison. He is a past winner of the prestigious 1999 ACM dissertation award—I believe no one has ever won this award more than once. He has proved many wonderful theorems and is one of the world experts in complexity theory.
Today I want to talk about a beautiful new game that he has created for Alice and Bob. The game is based on
The Bob in this game harks back to a vintage page of the ’90s. Vintage ’90s used to mean 1890’s, but now there is a museum of old webpages from the 1990’s. You can ask the Mystical Smoking Head of Bob a question, any question. He is all-powerful, but Alice wants to minimize her interaction with him.
I have had the pleasure to work on one project jointly with Dieter, and while that result was eclipsed by a result of Ryan Williams, I still consider our result a stepping stone for Ryan. Dieter just visited Georgia Tech and gave a talk in our theory seminar funded by the ARC center. It was a beautiful talk, about a great result, which I will now proceed to explain.
The Game for SAT
The game is played by two players: Alice and Bob, who else? They communicate back and forth, but only Alice sees the input, which is a set of 
Some notation: 
I sometimes wonder whether theory research would stop if the letter “
and I believe that this notation is due to the eminent Bernhard Riemann himself. In his famous paper that introduced the zeta function, he wrote 
The title of Riemann’s paper is: “Uber die Anzahl der Primzahlen unter einer gegebenen Grösse, or in English: On the Number of Primes Less Than a Given Magnitude. See here for a translation of the beautiful paper that changed number theory forever.
Back To The Game
Again the game is based on giving Alice a set of
Recall 
Her task is to determine whether or not they are satisfiable, which means that there is some assignment to the variables of boolean values 
As is often the case one player, in this case Alice, must run in polynomial time. Since there is no known algorithm that always runs in polynomial time for
But wait: she has the ability to ask Bob for help. Bob, unlike Alice in this game, is all-powerful: Bob can compute or determine anything that he wishes. Alice is allowed to ask questions by sending messages to Bob, who in turn sends back the correct answer—there is no issue of Bob being untruthful or cheating. Bob, in this game, is always going to answer the questions sent by Alice correctly.
That is the new game introduced by Holger Dell and Dieter in their paper. Pretty neat, no? The game so far is still uninteresting, we need to add one ingredient that makes it exciting:
Alice is charged by the number of bits she sends to Bob, and her task is to send as few bits as possible.
Now the game is interesting, very interesting. Without this restriction Alice could simply send all the clauses
to Bob, who would decide whether or not they were satisfiable, and then return one bit to Alice. With this restriction the game is much harder for Alice, and it is completely unclear what she should do? How many bits does she need in worst case to send to Bob? Note: Alice is only concerned with the length of the messages she sends to Bob, there is no restriction on the length of messages from Bob. Of course, Bob cannot send more than a polynomial number of total bits to Alice, since otherwise she would not run in polynomial time—just reading the messages would take too long.
Strategies For Alice
What does Alice do? In the initial version of the game—the free version—Alice is not allowed randomness. In the advanced version she is allowed to use randomness, but for now let’s restrict our attention to strategies that are deterministic.
possible clauses. So Alice could send Bob a bit vector of this length with a 
The Theorem
Dell and Dieter prove in their paper the following beautiful theorem:
Theorem: For any
, there is no strategy for Alice and Bob that allows Alice to send, in worst case, fewer than
bits of messages, unless the polynomial time hierarchy collapses.
Thus, up to an “epsilon” Alice’s best strategy is the simple one: send all the clauses to Bob, let him decide if they are satisfiable and wait for the answer to come back from Bob.
I find this surprising. It seems that there should be a better strategy for Alice, yet the theorem shows that no matter how she twists and turns, she must send about the same number of bits as the naive strategy. A pretty remarkable theorem. I will not attempt to describe the proof for two reasons. The usual: see their paper for the details—they explain it much better than I can. And the real reason—I do not yet understand the proof well enough to outline the main ideas. Perhaps I can do that in the future.
Open Problems
It the bound tight? Can the lower bound be improved? Or is there a strategy that slightly beats the naive one? Another very pretty open question is what happens when Alice is allowed randomness and the ability to make two-sided errors. That is Alice can be wrong either when she says yes or no: she must of course be right most of the time. Dieter and I discussed this question and it seems quite interesting.
Finally, there are two ways to view the game. One is that it shows that 
The answer to this may be obvious but I don’t immediately see it. Suppose one could prove unconditionally that
bits are necessary. What consequences would that have for the polynomial hierarchy? That is, is there anything like a converse to the theorem of Dell and Dieter?
Tim,
I believe that such an unconditional bound must imply P is not equal to NP. For if P=NP, then Alice can send zero bits to Bob.
The direction that excites me is: if you could prove that Alice solves with “only” sub-cubic bits, then there is a collapse seems the cool direction.
Oops — I thought I might be missing a trivial argument …
I think there’s a typo. Shouldn’t the theorem begin with “For any m ≥ 3 …”?
Josh J,
I am not sure why. Can you expand your point. The theorem says that Alice, in worst case, will need to send many bits. Of course this will only happen if she is given many clauses, and thus m will be big.
Your statement of the theorem begins,”For any c < 3 …". But the variable 'c' is not used elsewhere on this page. You seem to be using 'm' for the number of clauses. And unless I'm misunderstanding, m can only be big if m is first at least larger than 3 (that is, m ≥ 3).
Josh J,
Sorry if I was unclear. The point is Alice gets m clauses over n variables. Since they are 3-clauses the total input length can be as large as cubic in n. Actually using the usual encoding the total length is 3m\log n at most, where m is at most cubic in n.
The point of the theorem is that as a function of the number of variables the claim of Dieter is that worst case she will have to send more than n^c bits to Bob, for any fixed c<3. She can solve the problem if she is allowed to send order n^3 bits to Bob. But the theorem says that her trivial strategy is almost optimal.
Does that help?
Yes, now I understand! It’s for any fixed c < 3. Thanks for the explanation.
I’m missing something basic. How different is Bob from an advice string? Is the theorem that PH would collapse if there were an advice string of length 2^(n^a) for a < 3 that would let Alice decide SAT in poly(n) time?
Oops – I missed “no restriction in the length of the messages from Bob.” So it’s a sort of advice, where Alice can access a certain number of different strings, but each string can be of any length. Then PH collapses if 2^(n^a) strings suffice where a < 3.
Here is a non-paywalled link to the paper:
http://pages.cs.wisc.edu/~dieter/Papers/sparsification-stoc.pdf
The theorem applies to multi-round protocols, but according to the paper, the nonexistence of efficient _single-round_ protocols already implies many new results. (If I am not mistaken, this is the only way they use the theorem when proving their impressive list of corollaries.) Is is possible to bridge this gap, and prove unconditionally that the existence of efficient many-round protocols already implies the existence of efficient constant-round protocols?
Given any game, computational device, or dynamical engine (these three being fundamentally the same) it often is fun to ask “How can this game/device/engine be revisited/repurposed/reversed? What new theorems/laws/enterprises might be born?”
Applying this heuristic to the Dell-Dieter game, we suppose that Alice repurposes the game by constructing the input bit-by-bit, conditioning each new bit upon answers supplied by Bob. This strategy is of course mathematically legitimate: Alice has simply exercised her inalienable mathematical right to repurpose the Dell-Dieter game to construct (with Alice’s own resources in
, augmented by bit-limited queries to the oracle Bob) a class of inputs that is more interesting to Alice.
Then the Dell-Dieter theorem suggests (for example) the post-repurposing conjecture:
Conjectures like this help illuminate (for me) the poorly-understood yet intimate relation between concrete challenges assicated to construction, verification and validation (which engineers care about) and the fundamental mathematical challenges that are associated to the separation of complexity classes.
The repurposed Dell-Dieter game is an example of what Gödel’s Lost Letter and P=NP has called a “Burning Arrow” mathematical strategy. Also, Alice’s pragmatically motivated don’t-ask-permission repurposing of the game enjoyably echoes too the immortal Monty Python skit The Annoying Peasant. Similarly, a physician might counterintuitively inject an antigen to serve as a vaccine, an engineer might counterintuitively operate a Sterling power engine in reverse to serve as a refrigerator; or Leslie Nielsen might counterintuitively play a scene straight to serve as comedy. We are thus helped to an appreciation that reversal-of-purpose Burning Arrow strategies are ubiquitous in STEM/creative enterprises, and are a major reason that Gödel’s Lost Letter and P=NP is such a fun and thought-provoking weblog.
This inspires a nice competitive game: Alice knows the set of 3-clauses but Bob does not. Each turn, Alice asks a question and gets a correct answer in response. Bob then makes a guess as to the formula Alice has been given, using all the questions he’s been asked so far.
Alice’s goal is to determine whether the formula is satisfiable before Bob can determine what the clauses are (or an equivalent instance).
Probably Alice can win this game by asking a lot of dummy questions to lead Bob astray…
Let’s consider these two cases, separately:
1- m= n^(3-e),
2- m= \theta(n^3)
In the first case, Alice can construct the bit-vector and then, just send Bob the list of bits which are not zero. So, she needs to send less than $n^3$ bits:
$$m \log (8n^3)=3m+ 3m\log n = O(n^(3-e’))$$
For the second case, we have a very dense SAT instance ($m/n= n^2$). If a polynomial time algorithm exists which can solve “very dense” SAT instances, Alice can solve the SAT instance in polytime without communicating with Bob.
So, essentially to show that the polynomial time hierarchy collapses, one can try to find an efficient algorithm, i.e., a polynomial time algorithm, to solve very dense SAT instances.
Intuitively, I expected solving dense SAT instances to be easy but apparently, based on the handbook of satisfiability, in the worst-case, it is not the case.
> Another very pretty open question is what happens when Alice is allowed randomness and the ability to make two-sided errors.
I don’t get this one. If Alice can ask anything to Bob, then she could ask him random bits, isn’t it? The cost to Alice would be some constant, so how could allowing randomness change anything? Or maybe the key point is she could make two-sided errors?