home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / theory / 1707 < prev    next >
Encoding:
Text File  |  1992-07-28  |  999 b   |  30 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!munnari.oz.au!uniwa!bilby.cs.uwa.oz.au!wambenger!rowan
  3. From: rowan@cs.uwa.edu.au (Rowan Davies)
  4. Subject: Re: Complexity of Integer Programming.
  5. Message-ID: <1992Jul29.040913.14488@bilby.cs.uwa.edu.au>
  6. Sender: usenet@bilby.cs.uwa.edu.au
  7. Nntp-Posting-Host: wambenger
  8. Reply-To: (null)@cs.uwa.edu.au
  9. Organization: Uni of W. Aust.
  10. References: <1371@eagle.ukc.ac.uk>
  11. Date: Wed, 29 Jul 1992 04:09:13 GMT
  12. Lines: 16
  13.  
  14. In article 1371@eagle.ukc.ac.uk, jkp@ukc.ac.uk (J.K.Pearson) writes:
  15. >
  16. >Can some body answear me a simple question, what is the complexity of integer
  17. >programming, (I think it's NP complete but I'm not sure.)
  18.  
  19. It is definitely NP-Complete (or more precisely, NP-equivalent, since it
  20. is usually not a decision problem).  This can easily be shown by transforming
  21. satisfiability (or many other problems) to IP.
  22.  
  23. cheers......
  24.  
  25. Rowan Davies                University of Western Australia
  26. rowan@cs.uwa.edu.au         Pure Mathematics/Computer Science
  27.  
  28.  
  29.  
  30.