Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] How to Write Up Major Results

Expand Messages
  • Lance
    First some conference news: FOCS conference and hotel registration available on line, early deadline is September 30. STOC 2011 website is up with the CFP,
    Message 1 of 1 , Sep 7, 2010
      First some conference news: FOCS conference and hotel registration available on line, early deadline is September 30. STOC 2011 website is up with the CFP, deadline November 4. For more news follow the SIGACT Twitter or Facebook.

      Deolalikar's paper caused a stir in the community partly because it was written better than the usual P versus NP proofs we see. But the right comparison is to papers that have settled major questions, such as Agrawal, Kayal and Saxena's Primes in P and Omer Reingold's Undirected s-t Connectivity in Log Space.

      Both those papers needed to be convincing right off the bat and they both were. First notice the algorithms (page 3 in AKS and pages 9-12 in Reingold). No vague outline, no "should be able to", just very specific algorithms that one can analyze. Reingold only uses one "clearly" for the simple initial transformation from an adjacency matrix to  a rotation map.

      Both papers have to make two arguments, that the algorithms work in the claimed time/space and that they work correctly. In AKS, Section 4 shows the algorithm works correctly and Section 5 (using Lemma 4.3) show the algorithm runs in polynomial time. Section 4 is broken into a series of lemmas, each easily checkable with a limited knowledge of algebra. In Reingold the tricky part is getting the algorithm exactly right so that is uses logarithmic space which is carefully analyzed in his Sections 3 and 4. The correctness proof (based on earlier work) is a rather short Lemma 3.2 but Reingold does go over much of that background in Section 2.

      In both these results it took an amazing ingenuity to discover these algorithms, but it wouldn't take more than an undergraduate math major to check the proofs.

      Showing that P ≠ NP will be a much more difficult task, instead of coming up with a single algorithm, one has to show that no possible algorithm can solve some specific problem in NP. But even though the proof will be harder, the write-up needs to be just as understandable and easy to follow as AKS and Reingold. The community needs a proof we can verify step by step so that we can either be convinced of the proof or find the problem in the proof. If there is a jump in logic that one cannot verify the author has failed in his or her write-up.

      Proving P  ≠ NP will require pure genius but you shouldn't need a Fields medalist to verify the proof.

      Posted By Lance to Computational Complexity at 9/07/2010 07:43:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.