home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / theory / 1874 < prev    next >
Encoding:
Internet Message Format  |  1992-09-07  |  1.8 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!att!ulysses!allegra!selman
  2. From: selman@allegra.att.com (Bart Selman)
  3. Newsgroups: comp.theory
  4. Subject: Re: SAT
  5. Message-ID: <SELMAN.92Sep4154655@hunny.tempo.nj.att.com>
  6. Date: 4 Sep 92 19:46:55 GMT
  7. References: <1992Sep1.183853.5844@news.cs.indiana.edu>
  8. Sender: netnews@ulysses.att.com
  9. Reply-To: selman@allegra.att.com
  10. Organization: AT&T Bell Laboratories
  11. Lines: 31
  12. In-reply-to: pwp@moose.cs.indiana.edu's message of 1 Sep 92 18:38:36 GMT
  13.  
  14. Following up on Purdom's question about satisfiability
  15. algorithms, below are two other references that might be of
  16. interest. The first paper describes how to generate
  17. random formulas that are very hard for the Davis-Putnam
  18. procedure, and the second paper describes how a local search
  19. method substantially outperforms the Davis-Putnam procedure on such
  20. formulas. (I briefly reported on this work on the net before.)
  21.  
  22.   Bart Selman
  23.   AT&T Bell Laboratories
  24.  
  25. =====================================================
  26. Hard and Easy Distributions of SAT Problems
  27.    David Mitchell, Bart Selman, and Hector Levesque
  28.    Proc. of the Tenth National Conference on Artificial Intelligence 
  29.    (AAAI-92), San Jose, CA, July 1992, 459--465.
  30.  
  31. A New Method for Solving Hard Satisfiability Problems
  32.    Bart Selman, Hector Levesque, and David Mitchell,
  33.    Proc. of the Tenth National Conference on Artificial 
  34.    Intelligence (AAAI-92), San Jose, CA, July 1992, 440--446.
  35.  
  36. Papers are available via anonymous ftp:
  37.         ftp research.att.com
  38.         login: anonymous
  39.         password: [optional]
  40.         cd dist/ai
  41.         get hsat.ps.Z  % compressed postcript file
  42.         get gsat.ps.Z  % 
  43.    Let me (selman@research.att.com) know if you encounter any 
  44.    problems in printing the postscript file(s).
  45.