home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1850 < prev    next >
Encoding:
Internet Message Format  |  1992-08-31  |  2.2 KB
  1. Path: sparky!uunet!pmafire!news.dell.com!swrinde!cs.utexas.edu!sun-barr!ames!purdue!news.cs.indiana.edu!pwp@moose.cs.indiana.edu
  2. From: pwp@moose.cs.indiana.edu (Paul Purdom)
  3. Newsgroups: comp.theory
  4. Subject: SAT
  5. Message-ID: <1992Sep1.183853.5844@news.cs.indiana.edu>
  6. Date: 1 Sep 92 18:38:36 GMT
  7. Sender: root@news.cs.indiana.edu (Operator)
  8. Organization: Computer Science, Indiana University
  9. Lines: 31
  10.  
  11. This year there has been considerable interest in a simple greedy algorithm
  12. for finding a satisfying assignment of Boolean formulas in conjunctive
  13. normal form (SAT). The algorithm starts with an initial assignment of values
  14. to the variables. It then considers local changes to the assignment which
  15. reduce the number of clauses that are not satisfied. Algorithms of this
  16. nature have been published in
  17. 1. J. Gu, Efficient local search for very large-scale satisfiability problems,
  18. SIGART Bulletin 3(1):8-12, Jan. 1992.
  19. 2. Kazuo Iwama, Hidetoshi Abeta, and Eiji Miyano, Random Generation of
  20. Satisfiable and Unsatisfiable CNF Predicates, Algorithms, Software,
  21. Architecture, Information Processing 92, pp 322-328.
  22. 3. Elias Koutsoupias and Christos H. Papadimitrious, On the greedy algorithm
  23. for satisfiability, Information Processing Letters 43 (1992) pp 53-55.
  24.  
  25. Also this algorithm was mentioned this year or last on the net (I don't
  26. remember who mentioned it). Although it has long been known that an algorithm
  27. of this nature could be applied to the SAT problem, it appears that it was
  28. just this year (or last) that people became aware that this was a promising
  29. algorithm.
  30.  
  31. My question is: Does anyone know how it happened that a large number of
  32. researchers decided this year that this was a promising algorithm? Were there
  33. some earlier results on this algorithm, either published or unpublished, that
  34. increased the level of interest in this algorithm. In a quick reading of the
  35. above papers I did not see any indication of why the authors had chosen this
  36. algorithm to study. If I remember the note on this net correct, it took the
  37. view point that it was already common knowledge that this was a good
  38. algorithm. If so, it was common knowledge that I had been unaware of.
  39.  
  40. I will appreciate any help that people can give on trackinng down the origin
  41. of the recent interest in this algorithm.
  42.