Find an Error But Possible to Fix

Back to home page

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.

Advertisements

Yet to Find a Major Flaw

Back to home page

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.

Back to home page

Links to PDFs and Google Docs

Login: Guest

Password: Guest624

Latest Paper Draft (About 1.4MByte)

Links to the first version

Paper Verson 1.11 ,  Explanatory Notes Version 1.11 ,  Overview of the Shift Method (1.086MByte)

Google Docs for extra explanations to the 1st version

Sections 2 and 3

l-Extension,  Counting Marks,  Double Marks and Lemma 2.5Extension Generator Theorem 1,  Definition of Extension GeneratorEGT2  EGT3 ,  EGT4 , Split y of [n],  Relation to Sunflower .

Section 4

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

BlockedEdges I,   BlockedEdges IIBlockedEdges III, 

LocalShiftLemma by Lemma,

Edge Direction ProblemRegular σ Only.

Section 5

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

Links to Hamming Space papers

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

Back to home page

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.

Please download the latest pdf files  from the link below. I’m adding the 3rd file to provide short overall explanation of the shift method.

Paper Verson 1.11 (1.357MByte)

Explanatory Notes Version 1.11 (4.77MByte)

Overview of the Shift Method (1.086MByte)

Login: Guest

Password: Guest624

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

Back to home page

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