home *** CD-ROM | disk | FTP | other *** search
- Xref: sparky sci.math:14909 comp.theory:2404
- Newsgroups: sci.math,comp.theory
- Path: sparky!uunet!mcsun!sun4nl!ruuinf!hansb
- From: hansb@cs.ruu.nl (Hans Bodlaender)
- Subject: Re: NP Completeness Question
- Sender: network-news@cs.ruu.nl
- Message-ID: <1992Nov13.135722.27084@cs.ruu.nl>
- Date: Fri, 13 Nov 1992 13:57:22 GMT
- References: <1dpkkeINNad2@mizar.usc.edu> <BxMu2J.2JD@watserv1.uwaterloo.ca>
- Organization: Utrecht University, Dept. of Computer Science
- Lines: 43
-
- In <BxMu2J.2JD@watserv1.uwaterloo.ca> nrswart@phonon.uwaterloo.ca (Nicholas R. Swart) writes:
-
- >In article <1dpkkeINNad2@mizar.usc.edu> tunal@mizar.usc.edu (Tamer Unal) writes:
- >...
- >>My guess is that 1. is in of polynomial complexity while 2.
- >>is NP-complete.
- >>
- >>Any pointers, references, appreciated.
- >>
- >Professor E.R. Swart of the Computer Science Department at the University
- >of Guelph, has recently developed a polynomial-sized linear programing
- >formulation of the graph isomorphism problem and he has been able to show
- >that with minor modifications, this same formulation can be used to solve
- >the Hamilton tour, clique and other subgraph isomorphism problems.
- >
- >This proves that P=NP and all NP-complete and all other NP problems thus
- >have polynomial time algorithms.
- >
- >So to answer your question, 1 and 2 are probably both polynomial.
- >
- >Nicholas
- >Dept. of Elec. and Comp. Engineering
- >University of Waterloo
- >Waterloo, Ontario
- >CANADA
- >N2L 3G1
- >
- >>--
- >>Serdar Boztas
- >>posting from someone else's account with their permission
- >>normally at serdar@fawlty8.eng.monash.edu.au
-
- Ocasionnally, claims of results that P = NP appear. These have upto now all
- shown to be incorrect. So far, no-one has been
- able to give a correct proof of P=NP or the converse. Any claim of such a
- result should be doupted, before its proof is sufficiently verified.
- The result of professor Swart is not known to me, and I assume that it has not
- been verified by the scientific community, thus I think one should not base
- research on the assumption that the result claimed above is correct.
-
- Hans Bodlaender
- Dept of CS
- Utrecht University, the Netherlands
-