# Find an Error But Possible to Fix

During the verification with Google Docs, I found an error in Sec 5. I overlooked that f(σ) depends on z in the non-monotone case.

I think the error can be fixed with an improvement of Phase II of the extension generator theorem. I’m working on it now.

# Yet to Find a Major Flaw

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.

Google Docs for extra explanations to the 1st version

Sections 2 and 3

Section 4

DNF and Terms I,  DNF and Terms II,   Preprocess,   Quadruples σ,

LocalShiftLemma by Lemma,

Edge Direction ProblemRegular σ Only.

Section 5

Clique-Tail Pairs,  Fixed Point of (z, z’)First Two StepsSpace-Proportional Splits Step 3

l-extension Ext(U, l) becomes a majority when m is small and U is not too sparse  (Congressus Numerantium, 173(2005), 33–41)

Hamming Distance between Two Not Too Sparse m-Set Families is O( m / exp(-ln2 ln m) ), (Full version of the paper posted on 8/26/12. It improves the bound from O( m / ln m ). )

The sparsity of l-shadow of U is small as l gets smaller than m (Congressus Numerantium, 168(2004), 21–31. The definition of Ext(U, l) is slightly different in this old paper. It’s due to my try-and-errors.)

Some basic claims related to the Hamming space  (Congressus Numerantium, 161(2003), 41–63. )

# Verifying the Proof

I’ve been debugging the proof since I posted the previous version in this blog on 7/1. I tried hard to attack the proof from the opposite side. I found only minor bugs so far, and now start believing it.

I refined the paper and notes accordingly:  i) overview sections 4.3 for the monotone case, and 5.2 for the NP-NC construction newly added, ii) some technical proofs in Section 2 are moved to appendices, iii) minor error corrections, and iv) missing proof steps filled in.

Paper Verson 1.11 (1.357MByte)

Explanatory Notes Version 1.11 (4.77MByte)

Overview of the Shift Method (1.086MByte)

(Further small refinement on 9/15/12.)

The claims on the Hamming space in Sections 2 and 3 make the foundation of the shift method. The theory is developed to handle circuit complexity, especially of the clique problem. It has flavors in different areas:

1. Geometry: We want to find how the generated cliques intersect with each other at a node of circuit. (This is one general difficulty of treating circuit complexity.) It is about the topological properties of families of sets whose metric is the Hamming distance. It helps if we consider balls and spheres about an element.

2. Probability: Probabilistic arguments in combinatorics are mainly based on counting, because a considered probability space is discrete. In the Hamming space, sparsity of a family plays a similar role: it is about the ratio of #hits to the total number of elements. We focus on sparsity in relation to discrete topological properties of the Hamming space. It simplifies arguments.

3. Analysis: Theorem 2.1 adds some analytic flavor. We do asymptotic sparsity analysis.

4. Algebra: The operator of the domain is disjoint set union. We introduce the notion of a set generating another based on it. A family of sets generated by more than one generators is similar to ideal in the ring theory. On the other hand, disjoint set union doesn’t allow the closure property well, so it’s not easy to construct the theory in a complete algebraic system. However, it is very helpful to find a generator that generates almost every element in a subspace — it’s the extension generator theorem (Theorem 3.4). It can tell you that an element exists in your target subspace.

5. Extremal Set Theory in Combinatorics: It is important to know how elements in the Hamming space are related, especially intersected, to handle extremal sets. Theorem 3.4 has a strong link to Erdös and Rado’s sunflower lemma. In the previous post, I wrote that extension generators are a generalization of sunflower. To be more precise, Theorem 3.4 with Lemma 2.7 immediately implies the existence of a q-sunflower in most cases covered by the sunflower lemma. I explained it in the paragraph right after Proposition 3.7 in the paper.The theorem claims a stronger statement in such a way that if you extend m-sets into l-sets, almost all the cases of q disjoint l-sets with a small generator  contain a q-sunflower.

The mathematical structure of the Hamming space is intriguing. Please take a look at my past findings. Let U be a family of m-sets.

a) Its l-extension Ext(U, l) becomes a majority when m is small and U is not too sparse (please click): The main theorem means that if we remove k edges from an n-clique, almost all l-cliques are gone when lk is asymptotically larger than n2. For example, if k=n5/3, a majority of √n-cliques don’t exist  no matther which k edges are eliminated.

b) The Hamming Distance between Two m-Set Families (please click): If the sparsity of U is  O( m1-ε )  (ε: small constant), and we have a similar family U’, their Hamming distance is asymptotically smaller than m. The bound O(m / log m) is shown in the paper. There is a way to improve it into O(m / exp( log log  m) ).

# A Proof Draft of P≠NP

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 .

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