home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / theory / 1700 < prev    next >
Encoding:
Internet Message Format  |  1992-07-28  |  1.8 KB
  1. Path: sparky!uunet!utcsri!bonnie.concordia.ca!cerberus.ulaval.ca!news
  2. From: GautierA@vm1.ulaval.ca (Antoine Gautier)
  3. Newsgroups: comp.theory
  4. Subject: Re: Complexity of Integer Programming.
  5. Message-ID: <1992Jul28.175208.11058@cerberus.ulaval.ca>
  6. Date: 28 Jul 92 17:52:08 GMT
  7. References: <1371@eagle.ukc.ac.uk>
  8. Sender: news@cerberus.ulaval.ca
  9. Reply-To: GautierA@vm1.ulaval.ca (Antoine Gautier)
  10. Organization: Universite Laval
  11. Lines: 33
  12.  
  13. In article <1371@eagle.ukc.ac.uk> jkp@ukc.ac.uk (J.K.Pearson) writes:
  14. >  
  15. >  Can some body answear me a simple question, what is the complexity  
  16. of integer
  17. >  programming, (I think it's NP complete but I'm not sure.)
  18.  
  19. Yes it is! in its general form, IP includes TSP (traveling salesman)  
  20. as well as many other NP Complete subcases. 
  21.  
  22. refer to
  23. Garey and Johnson:
  24. Computers and intractability: a Guide to NP Completeness.
  25.  
  26. or
  27. Quayle, d.  "P = NP; the case P = 1..." (White house press).
  28.  
  29. -- NewsGrazer, a NeXTstep(tm) news reader, posting --
  30. M>UQR=&8P7&%N<VE[7&9O;G1T8FQ<9C!<9FUO9&5R;B!#;W5R:65R.WT*7&UA
  31. M<F=L,3(P"EQM87)G<C$R,`I<<&%R9%QT>#DV,%QT>#$Y,C!<='@R.#@P7'1X
  32. M,S@T,%QT>#0X,#!<='@U-S8P7'1X-C<R,%QT>#<V.#!<='@X-C0P7'1X.38P
  33. M,%QF,%QB7&DP7'5L,%QF<S,R($EN(&%R=&EC;&4@/#$S-S%`96%G;&4N=6MC
  34. M+F%C+G5K/B!J:W!`=6MC+F%C+G5K("A*+DLN4&5A<G-O;BD@=W)I=&5S.EP*
  35. M/B`@7`H^("!#86X@<V]M92!B;V1Y(&%N<W=E87(@;64@82!S:6UP;&4@<75E
  36. M<W1I;VXL('=H870@:7,@=&AE(&-O;7!L97AI='D@;V8@:6YT96=E<EP*/B`@
  37. M<')O9W)A;6UI;F<L("A)('1H:6YK(&ET)W,@3E`@8V]M<&QE=&4@8G5T($DG
  38. M;2!N;W0@<W5R92XI7`I<"EEE<R!I="!I<R$@:6X@:71S(&=E;F5R86P@9F]R
  39. M;2P@25`@:6YC;'5D97,@5%-0("AT<F%V96QI;F<@<V%L97-M86XI(&%S('=E
  40. M;&P@87,@;6%N>2!O=&AE<B!.4"!#;VUP;&5T92!S=6)C87-E<RX@7`I<"G)E
  41. M9F5R('1O7`I'87)E>2!A;F0@2F]H;G-O;CI<"D-O;7!U=&5R<R!A;F0@:6YT
  42. M<F%C=&%B:6QI='DZ(&$@1W5I9&4@=&\@3E`@0V]M<&QE=&5N97-S+EP*7`IO
  43. M<EP*475A>6QE+"!D+B`@(E`@/2!.4#L@=&AE(&-A<V4@4"`](#$N+BXB("A7
  44. 5:&ET92!H;W5S92!P<F5S<RDN"GT*
  45. `
  46.