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