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 $P=NP$ 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 $S(n)$ be the size of the optimal boolean circuit for SAT with an $n$ bit description. Conventional Wisdom says that $S(n)$ is super-polynomial, i.e. that $S(n)$ is larger than any polynomial $n^{k}$ for large enough $n$. We talk about what happens when $S(n)=O(n^{k})$ for some fixed $k$ in this post .

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

$S(n) \le n^{2}$ for infinitely many $n$;
$S(n) \ge 2^{\sqrt{n}}$ for infinitely many $n$.

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 $n$ cannot be made to work on other $n$‘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 $S(n)$ is small for some $n$, then certainly it must be small for all $n$ nearby. More precisely, $|S(n)-S(n+1)|$ cannot be very big. This follows directly from the ability to pad a set of clauses. Thus, if $S(n)$ 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 $S(n)$.

## 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 $n$ varies. Can we prove, even on some unproved assumptions, that $S(n)$ cannot vary wildly? This seems to be a very difficult problem.

Here is another problem that might be more attackable. Define $M(n)$ as the number of arithmetic operations that an optimal computation needs to perform $n \times n$ matrix multiplication. Can we prove that $M(n)$ 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 $M(n) < n^{\omega}$ infinitely often for some constant $\omega$, then $M(n) < n^{\omega}log n$ for all $n$ large enough. Clearly, there is nothing special about the function $n^{\omega}log n$, one can replace it by others. Also the same question makes sense for other problems.

1. May 30, 2009 1:37 pm

You state: “$|S(n)-S(n+1)|$ 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 $n$ bits to obtain an instance using precisely $n+1$ bits, unless one introduces a new input tape symbol. However, if a padding symbol is allowed, then the meaning of $S(n)$ changes, and it actually represents the size of the smallest circuit for any input requiring at most $n$ input symbols, and it is then monotonically non-decreasing. This would imply a lot more structure on $S(n)$ than you suggest. Yet, as an example, if it were the case that $S(n) = n^{\log^k n}$ for some fixed $k$ depending on the circuit type, then $S(n+1) - S(n)$ would appear to exhibit very large jumps. Or am I missing something?

May 30, 2009 3:34 pm

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?

• May 30, 2009 5:55 pm

Yes, that is illuminating. Thanks.