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