Edited 8/16 to correct attributions to Alon and Boppana and to Tardos, thanks to an anonymous commenter for the correction
Yesterday, Norbert Blum posted a preprint with a claimed proof that . An incorrect comment that I made last night and corrected this morning caused a lot of confusion, so let me apologize by summarizing the claims in the paper.
Coincidentally, this week, there is an Oberwolfach workshop on proof complexity and circuit complexity, so I am confident that by the end of the week we will hear substantive comments on the technical claims in the paper.
Recall that if a decision problem is solvable by an algorithm running in time on inputs of length then, for every , it is also solved, on inputs of length , by a circuit of size . Thus, if a problem is solvable in polynomial time it is also solvable by a family of polynomial size circuits (or, in short, it has polynomial circuit complexity).
The paper claims that Clique has exponential circuit complexity, and hence it has no polynomial time algorithm and . The argument leverages known results from monotone circuit complexity.
A monotone circuit is a boolean circuit that has only AND gates and OR gates, but does not have any NOT gates. A decision problem is a monotone problem if, for every fixed input length, it is solvable by a monotone circuit. For example, the problem to decide if a given -vertex graph has a clique of size at least is a monotone problem (if the input graph is presented as a boolean adjacency matrix), and so is the problem of deciding if a given graph has a perfect matching.
In the 1980s, Razborov proved that Clique cannot be computed by polynomial size monotone circuits. Later Andreev proved that there is a monotone problem in NP that requires exponential size monotone circuits, and Tardos Alon and Boppana proved that Clique itself requires exponential size monotone circuits. At the time, it was conjectured that if a monotone problem is in P, then it is solvable by a family of polynomial size monotone circuits. Under this conjecture, Razborov’s result would imply that Clique is not in P, and hence .
Unfortunately, Razborov refuted this conjecture, by showing that the perfect matching problem, which is in P, does not have polynomial size monotone circuits. Tardos showed that the Alon-Boppana exponential lower bound for clique holds for any monotone function sandwiched between the clique number and the chromatic number of a graph, including the Lovasz Theta function. Since the Theta function is polynomial time computable, and hence has polynomial size circuits, this shows that the gap between monotone circuit complexity and general circuit complexity can be exponentially large. (See first comment below.)
Razborov’s proof of the Clique lower bound for monotone circuits introduced the powerful approximation method. Roughly speaking, his approach was to start from a hypothetical polynomial size family of monotone circuits for Clique, and, from that, build a family of approximating circuits, which are just DNF formulas. The approximating circuits constructed by his method do not solve the Clique problem in general, but they solve a “promise” version of the problem, that is, they solve Clique on a certain subset of graphs. Then Razborov finishes the argument by showing that the approximating circuits are so simple that it is impossible for them to even solve Clique on that subset of inputs, thus reaching a contradiction to the assumption that there are monotone polynomial size circuits for Clique. The approximation method, variously modified, was also used to prove the lower bounds for Andreev’s problem and for matching.
Tim Gowers wrote a wonderful exposition of Razborov’s method, trying to show how one would come up with the various ideas, rather than just presenting the proof step by step.
Berg and Ulfberg simplify the proofs of Razborov, Andreev and Tardos for Clique and Andreev’s problem (but not for matching) by showing how to construct an approximator that has both small DNF complexity and small CNF complexity. The stronger claim makes an inductive argument in the construction easier to establish.
(At this point, I should clarify that I have never properly studies these results, so I am probably getting some details wrong. Please post corrections in the comments.)
The main claim in Blum’s paper is Theorem 6, which claims that if polynomial-size monotone circuits for a monotone problem admit a “CNF-DNF approximator” for a promise restriction of the problem (like the Berg-Ulfberg one), then also general circuits for the same problem admit such an approximator. Thus, if the approximator does not exist, it not only follows that the monotone complexity of the problem is super-polynomial, but also the general circuit complexity of the problem is superpolynomial.
Together with the Berg-Ulfberg approximator for monotone circuits for Clique, this implies that Clique is not in P.
Now, what could possibly go wrong with this argument?
- What about natural proofs?
This argument can only applied to (certain) monotone problems, and monotone problems are a vanishing fraction of all problems, hence one does not have the “largeness” property of natural proofs, and the argument is not a natural proof. (This is noted in the paper.)
- What about relativization and algebrization?
The argument starts from a boolean circuit for a given problem. If one is given an oracle circuit, with gates that answer oracle queries, or give evaluation of a polynomial extension of the problem, the argument cannot be applied.
- But this argument is lifting monotone circuit lower bounds to general circuit lower bounds, and so what about perfect matching, which has an exponential monotone circuit lower bound and a polynomial general circuit upper bound?
It is not known how to make the known lower bound for matching work via a “CNF-DNF approximator” and the claims in the paper only concern monotone lower bounds proved in this way. (Edited to add: but what about the Lovasz theta function?)
- But didn’t Razborov prove that the approximation method cannot prove a better-than-quadratic lower bound for general circuits?
Like any no-go theorem, Razborov’s impossibility result makes some assumption on what it means to “apply the approximation method to general circuits” and Blum claims that the assumptions do not apply to his argument.
- But where is the “heavy lifting” done? Shouldn’t every proof of a major result have one or more steps that are unlike anything done before?
I don’t have a good answer to this question. All the work is done in the proof of Theorem 6, which is the construction of the approximator starting from an arbitrary circuit. Maybe the argument is right and the heavy lifting was in Razborov’s work and subsequent extension and simplifications, and the fact that one can handle NOT gates at the bottom can be handled with an argument that is syntactically similar to previous work. Or, something goes wrong in the construction. Either way we will probably know soon.