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.
Like this:
Like Loading...
Related
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 most 
input 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.