home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2522 < prev    next >
Encoding:
Internet Message Format  |  1992-11-24  |  2.4 KB
  1. Path: sparky!uunet!munnari.oz.au!manuel.anu.edu.au!dubhe.anu.edu.au!nunki.anu.edu.au!not-for-mail
  2. From: jmr@cs.anu.edu.au (Mike Robson)
  3. Newsgroups: comp.theory
  4. Subject: Re: Silence on P=NP
  5. Date: 24 Nov 1992 10:40:25 +1100
  6. Organization: Computer Science Department, ANU, Australia
  7. Lines: 53
  8. Distribution: inet
  9. Message-ID: <1erq59INNonj@nunki.anu.edu.au>
  10. References: <1992Nov21.222755.18863@sophia.smith.edu> <1992Nov23.091136.7123@fwi.uva.nl> <1erksgINNom1@nunki.anu.edu.au>
  11. NNTP-Posting-Host: nunki.anu.edu.au
  12.  
  13. jmr@cs.anu.edu.au (Mike Robson) writes:
  14.  
  15. >leen@fwi.uva.nl (Leen Torenvliet) writes:
  16.  
  17. >>orourke@sophia.smith.edu (Joseph O'Rourke) writes:
  18.  
  19. >>>The silence on the Swart & Gismondi proof of P=NP is deafening.
  20. >>>Will no one venture an opinion?  My knowledge of linear programming
  21. >>>is insufficient to the task.
  22.  
  23. >>So is about everybody's it seems. I guess we're all waiting for some
  24.  
  25. >   If noone out there has understood the argument well enough yet to accept it
  26. >   or point out a flaw, why don't we pool our efforts to try and elucidate it?
  27.  
  28. >   Here's my comment to start the ball rolling:
  29. >      I am trying to understand the Graph Isomorphism paper first since that is the
  30. >      basis for the other two; I am fine as far as the end of page 5 where they talk
  31. >      about `a larger convex set $C_1$'. This seems to be the definition of $C_1$
  32. >      which crops up again significantly but I don't know which `larger convex set'
  33. >      it is supposed to be. Anybody like to clarify?
  34.  
  35.  
  36. Let me follow up my own article with another query:
  37.  
  38.  
  39. At the top of page 10 we are told (without proof) that every solution to
  40. F3 can be represented as  a linear combination of the $q$ vectors (with sum
  41. of coefficients equal to 1). Should this be obvious to me or is it the
  42. conclusion of some deep argument?
  43.  
  44. It seems to me that the space spanned by these $q$ vectors should have the
  45. same dimension as that spanned by the original permutation matrices, namely
  46. (n-1)^2+1 (since any n by n matrix is in the space provided all row and column
  47. sums are the same). But we know (page 8) that F3 is a formulation involving
  48. OMEGA(n^6) variables and O(n^5) constraints so I would expect its solution space
  49. to have dimension OMEGA(n^6) if it isn't empty. 
  50.  
  51. What is the simple point I am missing here?
  52.  
  53.  
  54.  
  55. >Dr J. M. (Mike) Robson,
  56. >Department of Computer Science,
  57. >Australian National University,
  58. >GPO Box 4,
  59. >Canberra, ACT 2601,
  60. >Australia.
  61.  
  62. >Tel: [61] 6-2494001
  63. >Fax: [61] 6-2490010
  64. >email: jmr@cs.anu.edu.au
  65.  
  66.