home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / 3138 < prev    next >
Encoding:
Internet Message Format  |  1992-08-18  |  1.2 KB
  1. Path: sparky!uunet!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!ucla-cs!ucivax!orion.oac.uci.edu!network.ucsd.edu!sdcc12!cs!demers
  2. From: demers@cs.ucsd.edu (David DeMers)
  3. Newsgroups: comp.ai
  4. Subject: Re: boolean satisfiability problem
  5. Message-ID: <36969@sdcc12.ucsd.edu>
  6. Date: 18 Aug 92 17:51:29 GMT
  7. References: <Bt5o1q.478@research.canon.oz.au>
  8. Sender: news@sdcc12.ucsd.edu
  9. Organization: =CSE Dept., U.C. San Diego
  10. Lines: 20
  11. Nntp-Posting-Host: beowulf.ucsd.edu
  12.  
  13. In article <Bt5o1q.478@research.canon.oz.au> naylor@research.canon.oz.au (William Naylor) writes:
  14. >I am looking for information on algorithms to solve the
  15. >"boolean satisfiability problem".  What is the largest problem that
  16. >can be solved routinely?  What is the best known algorithm?  
  17. >Any good references?
  18.  
  19. Cormen, Leiserson & Rivest have a chapter on approximation
  20. algorithms, but don't cover 3-CNF SAT.  You should get
  21. that book anyway though...
  22. Papadimitriou & Steiglitz is another reference.
  23.  
  24. Hope this is a start; somebody probably will give you
  25. exactly the right answer...
  26.  
  27.  
  28. -- 
  29. Dave DeMers             ddemers@UCSD   demers@cs.ucsd.edu
  30. Computer Science & Engineering    C-014        demers%cs@ucsd.bitnet
  31. UC San Diego                    ...!ucsd!cs!demers
  32. La Jolla, CA 92093-0114    (619) 534-0688, or -8187, FAX: (619) 534-7029
  33.