A Problem With Proving Problems Are Hard
Kannan’s famous theorem on boolean circuits and the polynomial hierarchy
Dick Karp is to blame. Without him we would not have the annoying P=NP question, without him we would not have thousands of problems all appearing to be hard to solve, without him modern computational complexity would be completely different.
Just to be clear—in case my words do not come across properly—we owe Dick a great debt. Without his work, his leadership, his brilliant insights, the field would be very different, and we owe him a great deal of thanks. Thanks Dick.
Today I will talk about an ancient result of Ravi Kannan proved in 1982, a beautiful result, yet still one of the few known general circuit lower bounds. There have been some other results proved since then, but Ravi’s result is a landmark. This result is related to a result of Karp and myself: Dick and I proved KL:
Theorem: If SAT has polynomial size circuits, then the polynomial time hierarchy (PH) collapses to .
This has been used both as a theorem and as a research direction over the years. A beautiful result, due to Jin-Yi Cai, is the huge improvement of this result to . I will discuss this result another time.
One key application of the KL theorem is in the proof of the beautiful result of Ravi Kannan. I will discuss how to try and avoid using our theorem—what am I thinking?—to prove his theorem.
A modern statement of Ravi’s theorem uses : this is the complexity class of sets so that for each length ,
where is the boolean complexity of the function
Theorem: For any , there is a set in so
Yes, Ravi actually proves more——but all my comments will apply to the stronger theorem, so I will only discuss in detail here.
Ravi’s first shows there is a language in such that
for all . He then uses KL in the following manner:
- The language SAT has polynomial size circuits: then by KL, PH hierarchy collapses to and therefore is in . Thus, in this case his theorem is true.
- The language SAT has super-polynomial circuits: in this case his theorem is also true. Note, SAT is in NP = .
Very neat. I pointed out once the great John Littlewood used a similar trick to prove a result in number theory:
- If the Riemann Hypothesis is true, then primes behave well and his theorem is true.
- If the Riemann Hypothesis is false, then primes behave poorly and his theorem is true.
So Ravi is in good company.
Kannan’s Proof—Can We Do Better?
There is an interesting issue with Ravi’s proof of his theorem—it is non-constructive and only shows there is a language with large circuits for infinitely many lengths . Let’s look at the proof again. The language is in and
is true for all . Suppose that SAT is in . Then, the PH hierarchy collapses to . Thus, is in and we are done.
However, suppose SAT is not in . Then, we only know that for an infinite number of lengths ,
So Ravi’s proof does not show the existence of the language for all . It only shows the existence for infinitely often.
I would like to construct an explicit language in so
for all . I cannot—yet. I have been working with Ken Regan on an approach, but it does not work.
How To Compare Circuits Fast
One reason Ravi needs is he needs to compare circuits to see if they are equivalent. Various others have since improved this step, getting with hardness for all , or with hardness for infinitely-many , but still short of what we would like. The following idea attempts to meld these improvements, and though it is basically known and gets only the result, perhaps it can be useful.
In any event it is a “trick” you may be able to use in other proofs, or to solve other problems. Many years ago I told this trick to Avi Wigderson—in the context of Kannan’s Theorem—and he said immediately to me:
How else could Ravi’s proof go?
Well Ravi’s proof does not use these ideas: obviously Avi figured out Kannan’s proof on his own. Oh well.
Let denote the two circuits and compute the same boolean function. Say a circuit with inputs is a -circuit provided only the inputs are used in any gate. The rest of the inputs are never used in a gate, and so have no effect on the output of the circuit. The key points of -circuits are the following lemmas:
Lemma: Let and be -circuits. Then, there is an algorithm to check if in time polynomial in and .
Proof: Clearly, we need only check the inputs used by the circuits to determine if they compute the same boolean function.
Lemma: Let be a -circuit, and let be a circuit on inputs. If , then there is a -circuit so , and
Proof: Let be the circuit with additional inputs
set to . It is easy to see and are equivalent. Also the complexity of cannot go up after setting variables to .
If we go over Ravi’s proof and only consider -circuits with , then equality will be checkable in polynomial time, thus saving an alternation. This will also avoid a technical lemma Ravi needs: he had to prove a special version of the classic Claude Shannon theorem that most boolean functions have exponential complexity. Note, we can use the original theorem on variables.
One could view the restriction to -circuits as a “padding” trick, which helps us compare circuits in polynomial time. This brings down the complexity of the whole operation to instead of . A similar method defines the complement of the language , thus achieving .
The main open problem I would like to see solved is the construction of hard boolean functions in weak complexity classes. Also, I would like to see a stronger form Ravi’s theorem which shows the existence of a language with large circuit complexity in proved for all —if this is possible.