home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / theory / 1775 < prev    next >
Encoding:
Text File  |  1992-08-18  |  1.2 KB  |  30 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!munnari.oz.au!metro!mama!naylor
  3. From: naylor@research.canon.oz.au (William Naylor)
  4. Subject: boolean satisfiability problem
  5. Message-ID: <Bt5Mz6.3xs@research.canon.oz.au>
  6. Sender: news@research.canon.oz.au
  7. Organization: Canon Information Systems Research Australia
  8. Date: Tue, 18 Aug 1992 01:04:17 GMT
  9. Lines: 19
  10.  
  11. I am looking for information on algorithms to solve the
  12. "boolean satisfiability problem".  What is the largest problem that
  13. can be solved routinely?  What is the best known algorithm?  
  14. Any good references?
  15.  
  16. The "boolean satisfiability problem" is a well-known NP-complete problem.
  17.  
  18. A boolean function is expressed as a product of sums, for example
  19.  
  20. F(a,b,c,d,...) = (a | ~b | c)&(~a | d | ~e)&...
  21.  
  22. where the variables can take on the values TRUE and FALSE, and '|' represents
  23. logical or, and '&' represents logical and.  The problem to be solved is:
  24. does any assignment of values to the variables cause the boolean function 
  25. F(...) to be TRUE?
  26. -- 
  27. William Naylor                               | naylor@research.canon.oz.au
  28. Canon Information Systems Research Australia | Phone +61 2 805 2000
  29. PO Box 313 NORTH RYDE NSW 2113               | Fax   +61 2 805 2929
  30.