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


16 thoughts on “Verifying the Proof

    • Hello

      Thanks very much or your reply. I’m with Toyota InfoTech Center to work on vehicular mobility and communication performance analysis.

      In theory I have Weighted planar separators are NP-hard to compute

      The online version of Chinese Postman Problem is computed efficiently.

      After moving to Toyota-ITC

      Presented at a workshop in Intl. Conference on Communications 09 as well


      At Indiana State Univ, I was devoting myself to the P-NP question from the view point of the Hamming space. I posted a couple of findings in Southeastern intl. conference on combinatorics, graph theory and computing during 2004-2006. One of them is posted in the blog as a): l-extension is a majority when m is small and U is not sparse. I think it’s a good one.

      Recently, I feel like returning to theory and working on the 3SAT critical density with a Rutgers WINLAB professor: its existence is open

      The P-NP question is my life-long obsession. Your technical comments/questions are welcome. Please let me know.

      Jun Fukuyama

    • Hello

      >suggest you create an “about” pg on your blog that lists these links & includes link to your linkedin profile (found that). fyi the 1st IEEE link above gets 404 error.

      Thanks. I’ll update my linkedin page. Let me attach the missing paper. It is presented at Vehicular Networking Conference 2009

      >whats the title of your Phd thesis? is there a link to it somewhere or maybe a pdf?

      It’s “and Approximability of Some Combinatorial Optimization Problems” from Penn State in 2001. I’m not sure there is a link to it. I can send it to you later (Right now I’m in Beijing for a conference)

      >Deolalikar proof from about 2.5yr ago. that was spearheaded to some degree by dick lipton thru his blog but also via polymath. have you ever tried emailing him?

      Thanks. I’ll try your suggestions. I haven’t been aware from these theory websites.

      >SJ told me youve submitted your P vs NP paper to a journal. can you say which one? how is that going?

      I submitted the material in Chap 1-4 to Transactions on Computation Theory. It wasn’t through unfortunately. The comments said that it is hard to understand clearly. I was thinking about adding more background and submit the NP\neNC result to J. of ACM or SIAM J. of computing. Somebody told me about Razborov’s “natural proof” paper: If you consider only inductive properties associated with nodes in a circuit, it is probably difficult to prove a big hardness like P\neNP or P\neNC. Not many people believe P\neNP is provable because of it. The NP\neNC construction in the blog paper is not a natural proof. The algorithm BlockedEdges2 chooses the best negative tail z among a majority such that the shift method works. Like I say in Sec 5.2, it is a fixed point argument, and it doesn’t exclude odd cases inductively. This part is non-natural It’s pretty hard to make everything absolutely right but I’ll keep trying.


  1. hi, interesting. suggest you create an “about” pg on your blog that lists these links & includes link to your linkedin profile (found that). fyi the 1st IEEE link above gets 404 error.

    the SAT transition pt is very interesting, probably still lots more to find there, have looked into that myself.

    whats the title of your Phd thesis? is there a link to it somewhere or maybe a pdf?

    just did some brief work to publicize your proof in two places. you should consider doing so yourself in other ways.

    (1) TCS stackexchange. chat section.

    (2) polymath wiki. made a new clearinghouse pg & put a link to it on the home pg, the latter already deleted but the former not (hope it sticks).

    to me its a shame your proof has apparently gotten no significant attn (or almost none whatsoever?) among the cyberspace community so far, which really jumped on the Deolalikar proof from about 2.5yr ago. that was spearheaded to some degree by dick lipton thru his blog but also via polymath. have you ever tried emailing him?

    SJ told me youve submitted your P vs NP paper to a journal. can you say which one? how is that going?

    • Hi

      Thanks for your question. Here is my answer:

      Classical barrier: you have a polynomial-sized Boolean circuit C to compute cliques. You want an input t to C that is a counter example: C returns yes even if t contains no l-clique, or returns no even if t contains an l-clique. In a non-monotone circuit, this is not easy. You assume that both children of a node \alpha have such counter examples t_1 and t_2, from which you try to construct t for \alpha. (t_i are actually counter examples to some logical properties) But t_1 \cup t_2 may have a contradiction. You must exclude these cases. Here “creating contradiction or not” touches the fundamental part of logic. It is very difficult to control its existence especially by induction.

      Fix in the paper: contradiction handling is not inductive on the depth of a node. Use the theory of Hamming space to enumerate as many t as possible at the root of C. (Each such t contains no l-cliques.) Then show that there always exists t with no contradiction. As summarized in Sec 5.2, it’s based on a fixed point argument looking at the whole Hamming space, rather than induction on depth.

      Jun Fukuyama

  2. I just got done taking a graduate class on NP-completeness. I don’t have the raw mathematical background to fully follow your proof, but I understand the significance if it does turn out to be correct.

    Good luck,
    Syler Clayton

    • Thanks for the link. This is new to me although I knew Deolaiker’s try.

      His approach is a whole different scenario from mine based on circuit complexity of CLIQUE. It’s a challenge for me to understand it. I’ll ask him to have a chat with me.


    • I know there are many other tries. The proof posted here is modular. Because of the long research, I am pretty sure that Sections 2-4 contains no major flaw. Sec 6 is beyond NP \ne NC. I felt I should be focused on Sec 5. If you find a specific error in the section, I would appreciate it very much. Right now, I’m working hard to make Sec2-4 more convincing. Please read google doc explanations now updated weekly

  3. hi. you credit some people in your acknowledgements at the end of the proof. do you think there is anyone who understands your papers other than you? is there anyone who can discuss it? are you willing to engage in an extended online chat on its contents? know of a place where we can chat openly online & would like to dig into your proof over some time in extended discussion but you’ll have to sign up for that.

    understand what you mean by m-sets. however right after that, am looking at your definition of l-extension at beginning. think you are probably defining something real here, but your symbolic definition makes no sense to me & right now dont think its using correct/logical mathematical grammar. is l-extension defined by anyone except you?

    • Thanks for your bit tough encouragement. Well, I’m right now in a long trip in Beijing, and don’t even have an access to my own blog due to the limited connection to the Internet. During this trip, I suddenly received feedbacks. I’m replying on iPod over wifi since PC doesn’t work for gmail.

      I am glad and willing to participate in online discussion after I go back to NJ.

      For the l-extension, I note your remark and will include an example of extension and its generator in a future version.

      Jun Fukuyama

  4. glad you have gotten some feedback. are you talking about feedback via email, not in blog comments? hope it is substantial & helpful. great you are open to chat. when are you finished travelling? my idea is to open an online chat room dedicated to discussion of your paper/results/research etc when you’re ready. the chat room in mind allows a leisurely back-and-forth that can happen intermittently/” as time permits” over days.

    think you’re on the right track & that you probably have substantial new results to some degree but imho right now the notation/formulation/presentation/style needs adjs & it has to be wired into existing research/literature in a more direct way…

    • I’ll go back to NJ on 12/23. Until then, I cannot update my blog. That’s the reason I’ve responded through mail only.

      Thanks for your help. I’ll mail you as soon as going back home about opening a chat room.

      Jun Fukuyama

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s