home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / doc / techrepo / 211 < prev    next >
Encoding:
Internet Message Format  |  1992-11-08  |  3.0 KB
  1. Path: sparky!uunet!ukma!usenet.ins.cwru.edu!agate!darkstar.UCSC.EDU!golding
  2. From: jean@cse.ucsc.edu (Jean McKnight)
  3. Newsgroups: comp.doc.techreports
  4. Subject: UCSC TR: Evidence for a Satisfiability Threshold for Random 3CNF Formulas
  5. Date: 7 Nov 1992 00:40:53 GMT
  6. Organization: University of California, Santa Cruz (CE/CIS Boards)
  7. Lines: 55
  8. Approved: compdoc-techreports@ftp.cse.ucsc.edu
  9. Message-ID: <1dfb6tINNrk5@darkstar.UCSC.EDU>
  10. NNTP-Posting-Host: oak.ucsc.edu
  11. Keywords: backtracking, logic, reasoning, satisfiability, threshold behavior.
  12. Originator: golding@oak
  13.  
  14.           University of California at Santa Cruz
  15. Baskin Center for Computer Engineering and Information Sciences 
  16.  
  17. The following technical report is available electronically or as
  18. a paper copy.  Instructions for getting either follow the abstract.
  19.  
  20.  
  21. UCSC-CRL-92-42   (available electronically, as ucsc-crl-92-42.ps.Z)
  22. EVIDENCE FOR A SATISFIABILITY THRESHOLD FOR RANDOM 3CNF FORMULAS
  23. Tracy Larrabee and Yumi Tsuji
  24. November 1992, 9 pages (paper copy $5.00)
  25.  
  26. Abstract:  This paper presents empirical evidence of a satisfiability
  27. threshold in random 3CNF formulas.  The paper also expands on and supports
  28. the conjecture of Mitchell, Selman, and Levesque that *hard* randomly
  29. generated CNF formulas will be hard for any reasonable satisfiability
  30. algorithm.  We report statistics for a much larger set of variables than
  31. have been previously reported; in particular, we show that for each clause
  32. to variable ratio less than 4.2, the percentage of satisfiable formulas 
  33. increases, and for each clause to variable ratio greater than 4.2, the
  34. percentage of satisfiable formulas decreases as a function of number of
  35. variables.  We found that several algorithms behaved qualitatively in the
  36. same fashion.  We report on the relative performance of each algorithm.
  37. Keywords:  backtracking, logic, reasoning, satisfiability, threshold behavior.
  38.  
  39.  
  40. This technical report is available electronically through either 
  41. of the following methods:
  42. 1.  through anonymous ftp from ftp.cse.ucsc.edu, in /pub/tr. Log in 
  43.     as "anonymous", use your email address as your password, specify 
  44.     "binary" before getting the file.  Uncompress before printing.
  45. 2.  by mail to automatic mail server rnalib@ftp.cse.ucsc.edu.
  46.     Put this command on the subject line or in the body of the message:
  47.     @@ send ucsc-crl-92-42.ps.Z from tr
  48.     To get the index or abstract list:
  49.     @@ send INDEX from tr
  50.     @@ send ABSTRACTS.1992 from tr
  51.     To get the list of the tr directory:
  52.     @@ list tr
  53.     To get the list of commands and their syntax:
  54.     @@ help commands
  55.  
  56. Order paper copies from:  Technical Library, Baskin Center for Computer 
  57. Engineering & Information Sciences, UCSC, Santa Cruz  CA  95064.
  58. Purchase orders are not accepted.  Checks or money orders must be
  59. for U.S. dollars, payable through a U.S. bank, and made out to 
  60. "UC Regents".
  61.  
  62. Questions:  jean@cse.ucsc.edu
  63.  
  64. ===========================================================================
  65. Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
  66.         compdoc-techreports-request@ftp.cse.ucsc.edu
  67.  
  68.  
  69.