A new game that helps us understand the structure of ${\mathsf{SAT}}$.

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 ${\mathsf{SAT}}$, 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 ${3}$-clauses: for example,

$\displaystyle x_{3} \vee x_{8} \vee \bar{x}_{11}, \ x_{11} \vee \bar{x}_{12} \vee x_{16}, \dots,$

Some notation: ${n}$ will always stand for the number of variables and ${m}$ for the number of clauses.

I sometimes wonder whether theory research would stop if the letter “${n}$” were banned from our papers? In number theory a complex number is usually denoted by

$\displaystyle s = \sigma + it,$

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 ${s = \frac{1}{2} + it}$ for a complex number ${s}$ on his famous line ${\sigma = \frac{1}{2}}$. Ken finds this notation macaronic for mixing Latin and Greek, when ${s = \sigma + i\tau}$ might seem more logical, but some have joked that Riemann used this notation because he forgot what Greek letter comes after ${\sigma}$.

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 ${3}$-clauses:

$\displaystyle C_{1},C_{2},\dots,C_{m}.$

Recall ${m}$ is the number of clauses and these clauses are over the variables ${\{x_{1},\dots,x_{n}\}}$.

Her task is to determine whether or not they are satisfiable, which means that there is some assignment to the variables of boolean values ${\{0,1\}}$, so that each clause evaluates to ${1}$.

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 ${\mathsf{SAT}}$, 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

$\displaystyle C_{1},C_{2},\dots,C_{m}$

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.

${\bullet}$ Alice could just send Bob all the clauses, but encoded cleverly. There are a total of

$\displaystyle 2^{3} \times {n \choose 3}$

possible clauses. So Alice could send Bob a bit vector of this length with a ${1}$ in the ${i^{th}}$ position if she has that clause. This is better than the naive ${O(n^{3}\log n)}$ encoding, but in worst case can be order ${n^{3}}$. Can Alice do better?

${\bullet}$ 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 ${n^{3}}$ bits to Bob, actually order ${n^{3}\log n}$, so it is worse than the first strategy.

${\bullet}$ Alice can allow Bob to take the lead. For example, Bob could send Alice a polynomial size string ${s}$ with Kolmogorov complexity near the length of ${s}$. 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.

${\bullet}$ Alice could ${\dots}$ Let’s stop here. You can think of your own strategies that are better than the ones that I suggested.

The Theorem

Dell and Dieter prove in their paper the following beautiful theorem:

Theorem: For any ${c<3}$, there is no strategy for Alice and Bob that allows Alice to send, in worst case, fewer than ${n^{c}}$ 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 ${\mathsf{SAT}}$ 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 ${n^{2.99999998}}$ total bits. Good hunting.

1. September 22, 2011 5:03 am

The answer to this may be obvious but I don’t immediately see it. Suppose one could prove unconditionally that $n^{3-\epsilon}$ 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?

September 22, 2011 7:52 am

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.

• September 22, 2011 10:14 am

Oops — I thought I might be missing a trivial argument …

September 22, 2011 6:08 am

I think there’s a typo. Shouldn’t the theorem begin with “For any m ≥ 3 …”?

September 22, 2011 7:54 am

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.

September 22, 2011 8:02 am

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).

September 22, 2011 8:13 am

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?

September 22, 2011 8:17 am

Yes, now I understand! It’s for any fixed c < 3. Thanks for the explanation.

September 22, 2011 12:31 pm

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?

September 23, 2011 11:46 am

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.

September 23, 2011 3:12 am

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?

6. September 23, 2011 8:34 am

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 ${P}$, 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:

Conjecture 1 For a specified Dell-Dieter query bound ${n^c}$, the class of SAT problems that Alice can construct-and-validate is strictly larger than ${P}$ for some ${c < 3}$. And yet, Alice cannot point to any concrete member of this class and say “This particular SAT problem is not in ${P}$.”

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.

7. September 23, 2011 9:48 am

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…

October 5, 2011 12:32 pm

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.