home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2425 next >
Encoding:
Internet Message Format  |  1992-11-15  |  1.1 KB
  1. Path: sparky!uunet!stanford.edu!agate!triangle.Berkeley.EDU!grove
  2. From: grove@triangle.Berkeley.EDU (Eddie Grove)
  3. Newsgroups: comp.theory
  4. Subject: Re: The P=NP question (was Re: NP Completeness Question
  5. Date: 15 Nov 1992 23:07:47 GMT
  6. Organization: University of California, Berkeley
  7. Lines: 15
  8. Distribution: inet
  9. Message-ID: <1e6l83INN1sv@agate.berkeley.edu>
  10. References: <Bxpv45.2I1@watserv1.uwaterloo.ca>
  11. NNTP-Posting-Host: triangle.berkeley.edu
  12.  
  13. In article <Bxpv45.2I1@watserv1.uwaterloo.ca> nrswart@phonon.uwaterloo.ca (Nicholas R. Swart) writes:
  14. >My attention has been drawn to the discussion about my work on the
  15. >P/NP conundrum.  Let me explain what has been going on.  My Ph.D.
  16. >student Stephen Gismondi and I have for some months been working on
  17. >the graph isomorphism problem and about three months ago I alighted
  18. >on a novel approach which seems to make everything fall into place. 
  19.  
  20. Could someone give a reference for graph isomorphism being NP-Complete?
  21.  
  22. I was not aware this had been proved.
  23.  
  24. It would still be interesting to see a poly-time algorithm for it if
  25. it is not known to be NP-Complete, of course.
  26.  
  27. Eddie Grove
  28.