Not a Natural Proof

Back to home page

I moved to Penn State as a postdoctoral fellow. Using weekends, I regularly update Google docs for extra explanation. This is meant to be another proof verification too. So far I’ve confirmed no major errors in Sections 1-4.

One common objection to a proof of big hardness through circuit complexity is so-called natural proof. Related links are found on the web: natural proof paper, wikipedia article, summary. Natural proof is a notion invented by Razborov and Rudich.

The paper says that a natural argument against a major hardness would create a Boolean circuit B that breaks a pseudo random number generator. Suppose that there is a proof P that a polynomial-sized Boolean circuit A cannot compute a problem in the target complexity class.  If P is natural, it is constructive, i.e., it designs a property C nodes in A should satisfy, checks it inductively from the leaves, and at the root of A, it draws a contradiction due to the confirmed property C. This type of argument itself creates a polynomial-sized circuit B; it’s discussed along the node structure of A.

By the largeness of natural P, the property C computed by B has a statistical significance, i.e., C’s occurrence probability is different from that in the pseudo random case. The algorithm B can be used to break a pseudo random number generator in polynomial time. Thus such P is unlikely to exist.

The proofs presented in Sections 5 and 6 in the paper here are not natural. The method in the monotone case (Sec. 4) is used as a tool box. It creates a relation between i) input: a negative tail (edge pattern outside target l-cliques), and ii) output: a shift (a conjunction of edges/non-edges in the DNF at the root of A). Enumerating all such pairs (input, output), the proof in Sec 5 concludes that there is an output with no contradiction in addition to no l-cliques contained.

The shift argument finds a fixed point of another similar relation at the root of A only. It is based on counting, creating no B as above. The natural proof paper also points out in the 2nd paragraph on page 6 that a counting-based discussion could be non-natural.

The precise condition the shift method checks is the following: there exists an edge set z,  a) of specified size, b) whose removal annihilates small cliques, and c) such that there is an element t in the DNF of the considered node, c)-1 whose positive literal set is disjoint with z,  and c)-2 whose negative literal set is contained in z.

This condition is not inductively maintained in the arguments in Sec. 5 and 6. The construction of t for given z is inductive, but is not aware of Condition c-2). It is for a monotone case allowing t to contain contradictions. A relevant edge set z is chosen at the root of A statistically in the framework of the Hamming space.

Hence a circuit B to break a random number generator is not created.

Back to home page