home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / theory / 1801 < prev    next >
Encoding:
Internet Message Format  |  1992-08-22  |  1.6 KB
  1. Path: sparky!uunet!mcsun!sun4nl!and!jos
  2. From: jos@and.nl (Jos Horsmeier)
  3. Newsgroups: comp.theory
  4. Subject: Re: boolean satisfiability problem
  5. Message-ID: <3277@dozo.and.nl>
  6. Date: 22 Aug 92 11:10:31 GMT
  7. References: <Bt5Mz6.3xs@research.canon.oz.au>
  8. Organization: AND Software BV Rotterdam
  9. Lines: 39
  10.  
  11. In article <Bt5Mz6.3xs@research.canon.oz.au> naylor@research.canon.oz.au (William Naylor) writes:
  12. |I am looking for information on algorithms to solve the
  13. |"boolean satisfiability problem".  What is the largest problem that
  14. |can be solved routinely?  What is the best known algorithm?  
  15. |Any good references?
  16. |
  17. |The "boolean satisfiability problem" is a well-known NP-complete problem.
  18. |
  19. |A boolean function is expressed as a product of sums, for example
  20. |
  21. |F(a,b,c,d,...) = (a | ~b | c)&(~a | d | ~e)&...
  22. |
  23. |where the variables can take on the values TRUE and FALSE, and '|' represents
  24. |logical or, and '&' represents logical and.  The problem to be solved is:
  25. |does any assignment of values to the variables cause the boolean function 
  26. |F(...) to be TRUE?
  27.  
  28. That reminds me ... Have a look at:
  29.  
  30. Wang, Hao. `Towards Mechanical Mathematics'
  31. IBM J. Research Develop. VOl. 4
  32. No. 1. January 1960.
  33.  
  34. This article describes exactly what you need: a method of deciding 
  35. whether or not a WFF in the propositional calculus is a theorem.
  36.  
  37. If you can find it (I think it's out of print for more than a decade
  38. now) you could have a look at:
  39.  
  40. John McCarthy
  41. Lisp 1.5 Programmer's Manual
  42. The MIT Press
  43. ISBN 0 262 13011 4
  44.  
  45. It describes a complete Lisp implementation of Wang's algorithm.
  46.  
  47. kind regards,
  48.  
  49. Jos aka jos@and.nl
  50.