home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14909 < prev    next >
Encoding:
Internet Message Format  |  1992-11-13  |  2.1 KB

  1. Xref: sparky sci.math:14909 comp.theory:2404
  2. Newsgroups: sci.math,comp.theory
  3. Path: sparky!uunet!mcsun!sun4nl!ruuinf!hansb
  4. From: hansb@cs.ruu.nl (Hans Bodlaender)
  5. Subject: Re: NP Completeness Question
  6. Sender: network-news@cs.ruu.nl
  7. Message-ID: <1992Nov13.135722.27084@cs.ruu.nl>
  8. Date: Fri, 13 Nov 1992 13:57:22 GMT
  9. References: <1dpkkeINNad2@mizar.usc.edu> <BxMu2J.2JD@watserv1.uwaterloo.ca>
  10. Organization: Utrecht University, Dept. of Computer Science
  11. Lines: 43
  12.  
  13. In <BxMu2J.2JD@watserv1.uwaterloo.ca> nrswart@phonon.uwaterloo.ca (Nicholas R. Swart) writes:
  14.  
  15. >In article <1dpkkeINNad2@mizar.usc.edu> tunal@mizar.usc.edu (Tamer Unal) writes:
  16. >...
  17. >>My guess is that 1. is in of polynomial complexity while 2.
  18. >>is NP-complete.
  19. >>
  20. >>Any pointers, references, appreciated.
  21. >>
  22. >Professor E.R. Swart of the Computer Science Department at the University
  23. >of Guelph, has recently developed a polynomial-sized linear programing
  24. >formulation of the graph isomorphism problem and he has been able to show
  25. >that with minor modifications, this same formulation can be used to solve
  26. >the Hamilton tour, clique and other subgraph isomorphism problems.
  27. >
  28. >This proves that P=NP and all NP-complete and all other NP problems thus
  29. >have polynomial time algorithms.
  30. >
  31. >So to answer your question, 1 and 2 are probably both polynomial.
  32. >
  33. >Nicholas
  34. >Dept. of Elec. and Comp. Engineering
  35. >University of Waterloo
  36. >Waterloo, Ontario
  37. >CANADA
  38. >N2L 3G1
  39. >
  40. >>-- 
  41. >>Serdar Boztas
  42. >>posting from someone else's account with their permission
  43. >>normally at serdar@fawlty8.eng.monash.edu.au
  44.  
  45. Ocasionnally, claims of results that P = NP appear. These have upto now all
  46. shown to be incorrect. So far, no-one has been
  47. able to give a correct proof of P=NP or the converse. Any claim of such a
  48. result should be doupted, before its proof is sufficiently verified.
  49. The result of professor Swart is not known to me, and I assume that it has not
  50. been verified by the scientific community, thus I think one should not base
  51. research on the assumption that the result claimed above is correct.
  52.  
  53.                 Hans Bodlaender
  54.                 Dept of CS
  55.                 Utrecht University, the Netherlands
  56.