home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2520 < prev    next >
Encoding:
Internet Message Format  |  1992-11-24  |  2.2 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!usenet.coe.montana.edu!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!GS35.SP.CS.CMU.EDU!sgall
  2. From: sgall+@CS.CMU.EDU (Jiri Sgall)
  3. Newsgroups: comp.theory
  4. Subject: Re: Silence on P=NP
  5. Message-ID: <By6xov.Muv.2@cs.cmu.edu>
  6. Date: 23 Nov 92 22:41:16 GMT
  7. Article-I.D.: cs.By6xov.Muv.2
  8. References: <1992Nov21.222755.18863@sophia.smith.edu> <1992Nov23.091136.7123@fwi.uva.nl> <By6nDC.6Gp@dcs.ed.ac.uk>
  9. Sender: news@cs.cmu.edu (Usenet News System)
  10. Organization: Carnegie Mellon University
  11. Lines: 30
  12. Nntp-Posting-Host: gs35.sp.cs.cmu.edu
  13.  
  14. In article <1992Nov21.222755.18863@sophia.smith.edu> you write:
  15. >The silence on the Swart & Gismondi proof of P=NP is deafening.
  16. >Will no one venture an opinion?  My knowledge of linear programming
  17. >is insufficient to the task.
  18.  
  19. To say the least, it's very poorly written. All the informal introductions 
  20. are just a random informal statements about P and NP that could be produced by
  21. any undergradute student who just passed an algorithms class. In a paper on 
  22. such results I would expect at least some nontrivial insight about the methods
  23. used and why should they work. Main results are stated as corollaries, no formal
  24. definitions, etc.
  25.  
  26. The technical parts introduce precisely some linear programming problem. Then
  27. the argument goes along the lines "this does not work but if you modify it in
  28. the following way, it will". Certainly not a way in which you write a proof in
  29. mathematics. Also things like talking about "a point in the convex hull of a
  30. larger convex set" do not give an impression that the authors have a good
  31. grasp on the subject.
  32.  
  33. My opinion is that nobody can take this writeup seriously. The papers should be
  34. rewritten completely so that they resemble a formal proof and than someone can
  35. check it. Probably the usual way would be to submit it in a journal or a 
  36. conference like FOCS/STOC.
  37.  
  38. Of course, if the proof is incorrect (which I believe is the case) then the
  39. best thing to do is to "publish" it as a poorly written unrefereed technical
  40. report - it certainly maximizes the time until the error is discovered.  
  41. (I think the ultimate version of this technique is due Fermat :-)
  42.  
  43. -- Jiri Sgall
  44.