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 , one of my favorite problems, as you may know.
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 -clauses: for example,
Some notation: will always stand for the number of variables and for the number of clauses.
I sometimes wonder whether theory research would stop if the letter “” were banned from our papers? In number theory a complex number is usually denoted by
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 for a complex number on his famous line . Ken finds this notation macaronic for mixing Latin and Greek, when might seem more logical, but some have joked that Riemann used this notation because he forgot what Greek letter comes after .
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 -clauses:
Recall is the number of clauses and these clauses are over the variables .
Her task is to determine whether or not they are satisfiable, which means that there is some assignment to the variables of boolean values , so that each clause evaluates to .
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 , Alice has a tough task. So far the game seems pretty unfair, and pretty boring—its just the satisfaction problem. Nothing new.
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.
Alice could just send Bob all the clauses, but encoded cleverly. There are a total of
possible clauses. So Alice could send Bob a bit vector of this length with a in the position if she has that clause. This is better than the naive encoding, but in worst case can be order . Can Alice do better?
Alice could start to send clauses to Bob, one at a time. Each time she asks him whether or not the clauses he has seen so far have more than a polynomial number of satisfying assignments. If they ever have only a polynomial number, then Bob will send all of them to Alice. She then can check the rest of the clauses. A reasonable strategy: Alice is being conservative and not sending all the clauses at once. But it is not hard to create examples where this will require her to send all the clauses to Bob. Thus it will send over bits to Bob, actually order , so it is worse than the first strategy.
Alice can allow Bob to take the lead. For example, Bob could send Alice a polynomial size string with Kolmogorov complexity near the length of . Alice, being polynomial time limited, has no hope of constructing such a string, but Bob is all powerful and can send her such string. The work of Eric Allender, Harry Buhrman, Michal Koucky, Dieter, and Detlef Ronneburger show that having access to such strings can be very powerful. But it turns out that even with this help, Alice cannot determine the state of her clauses in polynomial time.
Alice could Let’s stop here. You can think of your own strategies that are better than the ones that I suggested.
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.
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 is incompressible, and the other is that the game could be a pathway to a proof that the polynomial hierarchy really does collapse. Of course the conventional wisdom is that the hierarchy is strict, but as I have said many times before: who knows? What Dieter has supplied is an intriguing new approach to show the hierarchy does indeed collapse: find a strategy for Alice that sends only total bits. Good hunting.