# A Nightmare about SAT

* SAT could be easy and hard *

Sigmund Freud was not a famous computer scientist. He is of course famous for being ”the father of psychoanalysis,” and pioneered the study of dream symbolism, especially nightmares. I have a recurring dream about that you might characterize as a ”nightmare.” I hope by telling you my nightmare, I will stop having it–perhaps my telling it will be therapeutic.

## The Nightmare

There are several versions of my nightmare, but they all concern whether or not the complexity of NP can vary wildly. Suppose that we focus on the boolean circuit complexity of SAT. The same comments can be made about uniform complexity, but they are more straightforward for circuit complexity so we we will only consider circuit complexity.

Let be the size of the optimal boolean circuit for SAT with an bit description. Conventional Wisdom says that is super-polynomial, i.e. that is larger than any polynomial for large enough . We talk about what happens when for some fixed in this post .

The troubling possibility, to me, is that could vary wildly as tends to infinity. For all we know it could be the case that * both * the following are true:

for infinitely many ;

for infinitely many .

This would be a terrible situation, since then sometimes SAT is ”easy” and sometimes SAT is ”hard”. At first blush you might think that this is impossible. If SAT is easy infinitely often, then how could it be the case that the method that works on some cannot be made to work on other ‘s. The nightmare is that this seems completely possible. There seems to be no way to argue that it cannot happen.

One can easily prove if is small for some , then certainly it must be small for all nearby. More precisely, cannot be very big. This follows directly from the ability to pad a set of clauses. Thus, if varies from easy to hard, the corresponding places must be far apart. But that is the only restriction that I can see on the behavior of the function .

## Open Problems

An important open problem, in my opinion, is to resolve this question about SAT. Call the behavior of a problem * wild * if the corresponding complexity function varies greatly as varies. Can we prove, even on some unproved assumptions, that cannot vary wildly? This seems to be a very difficult problem.

Here is another problem that might be more attackable. Define as the number of arithmetic operations that an optimal computation needs to perform matrix multiplication. Can we prove that cannot be a wild problem? The reason this seems possible is the potential to use the famous insight of Strassen: the recursive structure of matrix multiplication. I think this question might be resolvable. A concrete version would be to show that if infinitely often for some constant , then for all large enough. Clearly, there is nothing special about the function , one can replace it by others. Also the same question makes sense for other problems.

You state: “ cannot be very big”. Does this not depend on the specific encoding? For the obvious fixed encodings it does not seem trivial to pad an instance using bits to obtain an instance using precisely bits, unless one introduces a new input tape symbol. However, if a padding symbol is allowed, then the meaning of changes, and it actually represents the size of the smallest circuit for any input requiring

at mostinput symbols, and it is then monotonically non-decreasing. This would imply a lot more structure on than you suggest. Yet, as an example, if it were the case that for some fixed depending on the circuit type, then would appear to exhibit very large jumps. Or am I missing something?What I had in mind is quite simple. Suppose you wish to solve a k variable m clause problem. But assume that you have access to a k-1 variable m clause oracle. Using self reduction it is easy to see that you can use the oracle to solve your problem with at most two calls: try the extra variable as 0 and as 1.

This self reduction, for any reasonable encoding, can be used to show that the cost of S(n) and S(n+1) cannot vary too much.

Does this help?

Yes, that is illuminating. Thanks.

It might be that wildness and hardness might have some deeper relationship than just the behavior of S. A typical proof approach for “tameness” would be to show a “nice decomposition” of the problem into smaller ones. It is this very decomposition property that is also typical for efficient algorithms.