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 n^{1/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

### Like this:

Like Loading...