Jun Fukuyama's P≠NP Paper

Jun Fukuyama has been working on P vs NP for 10 yrs and created a blog, Jun Fukuyama's P≠NP Page on Jul 1 2012 to announce his recent proof. (its technically a proof to separate NP from P/Poly, the class of polynomial-size circuits.)

the site has several papers. the main paper is 60 pages. there are several slideshow summaries/presentations/overviews including handwritten notes and diagrams and additional explanatory material.

Fukuyama has emailed some leading complexity theory professors/researchers announcing it. apparently none have responded publicly so far. this is in strong contrast to the Deolalikar paper which received significant media attention and which many leading complexity theorists and mathematicians quickly and publicly started analyzing in cyberspace blogs and comments only days after it was initially announced.

the 1st two entries so far on the blog dated Jul 1 and Aug 26. from the blog, "It’s a generalization of Razborov-Alon-Boppana proof of super polynomial monotone circuit complexity to compute cliques." he states in a blog comment the paper is submitted to Transactions on Computation Theory. he has posted and replied to comments on his blog. from the paper:

Acknowledgement: The author would like to thank Professors Martin Fu ̈rer at Penn State, Osamu Watanabe at Tokyo Institute of Technology, and Eric Allender at Rutgers University for their good suggestions. Also, it has been very helpful of Professors Tadao Saito at the University of Tokyo and Hisashi Kobayashi at Princeton University to provide supports toward the submission of this paper.

From his LinkedIn profile, Fukuyama was an Assistant Professor at Indiana State University 2001-2006 teaching undergraduate and graduate courses in computer science. also from the profile he has over a half dozen published papers in computer science and electrical engineering. he has a PhD in Theoretical Computer Science from Penn State University. his PhD dissertation is entitled "Approximability of Some Combinatorial Optimization Problems", 2001.

Fukuyama has joined the stackexchange TCS theory site as user "jun" and participated in an extensive online discussion in the chat room, has made and posted new google notes for clarifications in response, and is making modifications to the proof based on the discussion.

Fukuyama has a few published peer-reviewed papers in theoretical computer science or complexity theory. the main intermediate papers utilized in the proof on Hamming code theory were published in "Congressus Numerantium", Southeastern International Conference on Combinatorics, Graph Theory, and Computing. his published peer reviewed papers are mainly with Piotr Berman (Assoc prof, Penn State U) as the lead author.

some of the elements/concepts/claims of the paper include

• extremal set theory, set families
• concepts of the density vs sparsity of sets
• lemmas on hamming spheres
• claim on a stronger erdos sunflower lemma
• analysis of constant-size circuit minterm structure ("m-sets") but so far not referring to "minterms"
• induction on the monotone circuit

the argument appears to be based on processing the DAG representing the circuit in an inductive way. there are claims that intermediate nodes of the circuit must find cliques of some certain size/structure/density. various algorithms that process the circuit are presented. the final claim is that a contradiction ensues, that after the inductive process a clique is found that the circuit cannot recognize. this all leads to a NP != NC proof that is later generalized to P != NP (more technically the stronger claim that NP != P/Poly, although P/Poly is not referred to by name in the current rev of the paper).

discussion:

• hacker news reaction/discussion/commentary of proof, links, etc
• monotone circuits chat room off of cstheory.stackexchange.com. live chat room discussion with Fukuyama with background, many related links re Razborovs natural proofs barrier & Chows & Liptons counterarguments, points of the proof, etc, opened ~1/1/2012
• a set of bookmarked links/comments from the chat session. related papers/links eg to Harpers theorem on Hamming spheres.
• Jun Fukuyama student reviews on ratemyprofessor.com