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

Advertisements

Yet to Find a Major Flaw

Back to home page

I’m recently active in stack exchange. (http://cstheory.stackexchange.com/) I’ve decided to refine the paper according to the discussions there.  The definition of sparsity will be more generalized.

The sticky post on the top collects all the related links. Especially, the google docs include extra explanations.

I’ll keep updating them on weekly basis.

I also gathered my old Hamming distance papers in the sticky post. Their motivation was actually this research: Let’s say a node in a Boolean circuit is an AND gate a=a1 ∧ a. An l-clique c is generated at a if the edges of c implies a. Inductively we have two sets of l-cliques generated at a1 and a. It takes a theory to figure out which cliques are generated at a. I first thought minimum Hamming distance could tell something important about it. It was short for the clique complexity. I moved to the l-extension after doing hard research.

Back to home page

A Proof Draft of P≠NP

Back to home page

My name is Jun Fukuyama. I’m currently a researcher at Toyota InfoTechnology Center. I’m visiting WINLAB and Civil Engineering department at Rutgers University, working on algorithms and mathematical analysis related to vehicular communications and mobility modeling.

I have been working on the P-NP question for over 10 years since my last years of PhD. Recently I came up with a possible proof .

Here are the links:

Paper Verson 1.01 (1.20MByte)

Explanatory Notes Version 1.01 (4.29MByte)

Login: Guest

Password: Guest624

(1/20/13: The above old links are deleted. )

The proof is to show that the circuit complexity of CLIQUE is exponential. It’s a generalization of Razborov-Alon-Boppana proof of super polynomial monotone circuit complexity to compute cliques. The section structure is:

Sec 2 and 3: Develop tools in the Hamming space. Show a generalization of Erdös and Rado’s sunflower lemma.

Sec4: Prove the exponential monotone circuit complexity of clique using the result of Sec 3.

Sec5: Based on 4, show that a Boolean circuit of polynomial size and polylog depth cannot compute the n1/4-clique problem.

Sec 6: Remove the polylog depth constraint graph theoretically. As a result, any polynomial sized circuit does not compute the clique problem.

The proof is complicated. However, please take a look at both the paper and notes at once.  I think it’s a good way to share mathematical ideas.

Your comments are appreciated! Please give me feedback. (The comment button is right next to the title.)

Back to home page