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)
(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.)