home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14906 < prev    next >
Encoding:
Internet Message Format  |  1992-11-13  |  2.1 KB
  1. Xref: sparky sci.math:14906 comp.theory:2402
  2. Path: sparky!uunet!wupost!sdd.hp.com!spool.mu.edu!agate!doc.ic.ac.uk!uknet!qmw-dcs!pef
  3. From: pef@dcs.qmw.ac.uk (Panayotis Fouliras; TA PhD)
  4. Newsgroups: sci.math,comp.theory
  5. Subject: Re: NP Completeness Question
  6. Message-ID: <1992Nov13.114038.16511@dcs.qmw.ac.uk>
  7. Date: 13 Nov 92 11:40:38 GMT
  8. References: <1dpkkeINNad2@mizar.usc.edu> <BxMu2J.2JD@watserv1.uwaterloo.ca>
  9. Sender: usenet@dcs.qmw.ac.uk (Usenet News System)
  10. Organization: Computer Science Dept, QMW, University of London
  11. Lines: 42
  12. Nntp-Posting-Host: sequent.dcs.qmw.ac.uk
  13.  
  14. In <BxMu2J.2JD@watserv1.uwaterloo.ca> nrswart@phonon.uwaterloo.ca (Nicholas R. Swart) writes:
  15.  
  16. >In article <1dpkkeINNad2@mizar.usc.edu> tunal@mizar.usc.edu (Tamer Unal) writes:
  17. >...
  18. >>My guess is that 1. is in of polynomial complexity while 2.
  19. >>is NP-complete.
  20. >>
  21. >>Any pointers, references, appreciated.
  22. >>
  23. >Professor E.R. Swart of the Computer Science Department at the University
  24. >of Guelph, has recently developed a polynomial-sized linear programing
  25. >formulation of the graph isomorphism problem and he has been able to show
  26. >that with minor modifications, this same formulation can be used to solve
  27. >the Hamilton tour, clique and other subgraph isomorphism problems.
  28.  
  29. >This proves that P=NP and all NP-complete and all other NP problems thus
  30. >have polynomial time algorithms.
  31.  
  32. >So to answer your question, 1 and 2 are probably both polynomial.
  33.  
  34. >Nicholas
  35. >Dept. of Elec. and Comp. Engineering
  36. >University of Waterloo
  37. >Waterloo, Ontario
  38. >CANADA
  39. >N2L 3G1
  40.  
  41. If this is so, could you please provide with a
  42. pointer/reference to a publication, where the above is
  43. described (preferably not Technical Reports, which are more
  44. diffcult to access)?
  45.  
  46. Thank you in advance
  47.  
  48. Panayotis
  49. --
  50. UUCP:      pef@qmw-dcs.uucp  | Computer Science Dept    | "H Rwmania
  51. Internet:  pef@dcs.qmw.ac.uk | QMW University of London |  kai an
  52. JANET:     pef@uk.ac.qmw.dcs | Mile End Road            |  eperasen,
  53. Voice:     +44 71 975 5220   | London E1 4NS            |  anthei kai
  54. FAX:       +44 81 980 6533   |                          |  ferei kai
  55. Cellphone: Too expensive to fit                            allon"
  56.