home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14895 < prev    next >
Encoding:
Internet Message Format  |  1992-11-13  |  1.4 KB
  1. Xref: sparky sci.math:14895 comp.theory:2401
  2. Newsgroups: sci.math,comp.theory
  3. Path: sparky!uunet!utcsri!torn!watserv2.uwaterloo.ca!watserv1!phonon.uwaterloo.ca!nrswart
  4. From: nrswart@phonon.uwaterloo.ca (Nicholas R. Swart)
  5. Subject: Re: NP Completeness Question
  6. Message-ID: <BxMu2J.2JD@watserv1.uwaterloo.ca>
  7. Sender: news@watserv1.uwaterloo.ca
  8. Organization: University of Waterloo
  9. References: <1dpkkeINNad2@mizar.usc.edu>
  10. Date: Fri, 13 Nov 1992 02:11:06 GMT
  11. Lines: 29
  12.  
  13. In article <1dpkkeINNad2@mizar.usc.edu> tunal@mizar.usc.edu (Tamer Unal) writes:
  14. ...
  15. >My guess is that 1. is in of polynomial complexity while 2.
  16. >is NP-complete.
  17. >
  18. >Any pointers, references, appreciated.
  19. >
  20. Professor E.R. Swart of the Computer Science Department at the University
  21. of Guelph, has recently developed a polynomial-sized linear programing
  22. formulation of the graph isomorphism problem and he has been able to show
  23. that with minor modifications, this same formulation can be used to solve
  24. the Hamilton tour, clique and other subgraph isomorphism problems.
  25.  
  26. This proves that P=NP and all NP-complete and all other NP problems thus
  27. have polynomial time algorithms.
  28.  
  29. So to answer your question, 1 and 2 are probably both polynomial.
  30.  
  31. Nicholas
  32. Dept. of Elec. and Comp. Engineering
  33. University of Waterloo
  34. Waterloo, Ontario
  35. CANADA
  36. N2L 3G1
  37.  
  38. >-- 
  39. >Serdar Boztas
  40. >posting from someone else's account with their permission
  41. >normally at serdar@fawlty8.eng.monash.edu.au
  42.