home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / theory / 2709 < prev    next >
Encoding:
Internet Message Format  |  1992-12-15  |  3.0 KB
  1. Path: sparky!uunet!munnari.oz.au!manuel.anu.edu.au!dubhe.anu.edu.au!nunki.anu.edu.au!not-for-mail
  2. From: jmr@cs.anu.edu.au (Mike Robson)
  3. Newsgroups: comp.theory
  4. Subject: P=NP??? $50,000
  5. Date: 16 Dec 1992 10:18:57 +1100
  6. Organization: Computer Science Department, ANU, Australia
  7. Lines: 68
  8. Distribution: inet
  9. Message-ID: <1glp51INN1gg@nunki.anu.edu.au>
  10. NNTP-Posting-Host: nunki.anu.edu.au
  11. Summary: The proof is clearly wrong
  12. Keywords: Money
  13.  
  14.  
  15.  
  16. >Newsgroups: comp.theory
  17. >Path: gene.fwi.uva.nl!fwi.uva.nl!sun4nl!mcsun!uunet!zaphod.mps.ohio-state.edu!uwm.edu!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watserv1!phonon.uwaterloo.ca!nrswart
  18. >From: nrswart@phonon.uwaterloo.ca (Nicholas R. Swart)
  19. >Subject: S. Gismondi and E.R. Swart's research reports.....
  20. >Message-ID: <ByJIsL.B4y@watserv1.uwaterloo.ca>
  21. >Sender: news@watserv1.uwaterloo.ca
  22. >Organization: University of Waterloo
  23. >Date: Mon, 30 Nov 1992 17:48:20 GMT
  24. >Lines: 20
  25.  
  26. [a few lines omitted]
  27.  
  28. >So far things are looking very good. In an earlier post someone said they
  29. >would put $10,000 down that the proof is correct. I'll raise that to
  30. >$50,000.
  31. >
  32. >Nicholas Swart
  33. >Dept. of Elec. and Comp. Engineering
  34. >University of Waterloo
  35. >Waterloo, Ontario
  36. >CANADA
  37. >N2L 3G1
  38. >
  39. >
  40.  
  41. If this offer has not been withdrawn yet, I hereby accept.
  42.  
  43. The ways in which the proof is incorrect are at least three. Of course
  44. only one step needs to be incorrect for the whole proof to be incorrect.
  45.  
  46. 1. The isomorphism paper relies on a claim that "Every solution to formulation
  47. F3 can be represented by an expression of the form"
  48. t = \sum \alpha _i q_i;
  49. no proof of this claim is made and the authors do not know a proof.
  50.  
  51. 2. The main theorem of the isomorphism paper is not merely unproven
  52. but invalid. I have already posted a counterexample to comp.theory.
  53.  
  54. 3. The "N=1" paper's claim for solution of NP-Complete problems would
  55. not follow even if the theorem of the isomorphism paper were correct.
  56. In detail corollary 1 of the isomorphism paper (which would be valid
  57. if the theorem were valid) relies on the fact that if Ta=b and T has nonzero
  58. entries wherever Q does (and T has no negative entries), Qa has nonzero
  59. entries which are a subset of the nonzero entries of Ta (i.e. of b)
  60. and so, since Qa has the same number of nonzero entries as b, it follows that
  61. Qa=b.
  62. In the claimed proofs of linear programming formulations of NP-Complete
  63. problems in the "N=1" paper, there is no such argument possible, since
  64. we have merely a condition that Ta= some matrix with specified values
  65. in a subset of its entries; this is not sufficient to prove Qa= another
  66. such matrix.
  67.  
  68. Deficiency 1 in the proof can perhaps be fixed (I believe the assertion
  69. is probably valid but I can't prove it). Deficiency 3 can possibly be
  70. overcome by a completely new argument (I doubt it). Deficiency 2 is fatal.
  71. I do not know that the algorithm is incorrect but the proof definitely is.
  72.  
  73.  
  74. You can send the cheque to
  75.  
  76. Dr J. M. Robson,
  77. Department of Computer Science,
  78. Australian National University,
  79. GPO Box 4,
  80. Canberra, ACT 2601,
  81. Australia.
  82.