🚀 go-pugleaf

          University of California at Santa Cruz
Baskin Center for Computer Engineering and Information Sciences 

The following technical report is available electronically or as
a paper copy.  Instructions for getting either follow the abstract.


UCSC-CRL-92-42   (available electronically, as ucsc-crl-92-42.ps.Z)
EVIDENCE FOR A SATISFIABILITY THRESHOLD FOR RANDOM 3CNF FORMULAS
Tracy Larrabee and Yumi Tsuji
November 1992, 9 pages (paper copy $5.00)

Abstract:  This paper presents empirical evidence of a satisfiability
threshold in random 3CNF formulas.  The paper also expands on and supports
the conjecture of Mitchell, Selman, and Levesque that *hard* randomly
generated CNF formulas will be hard for any reasonable satisfiability
algorithm.  We report statistics for a much larger set of variables than
have been previously reported; in particular, we show that for each clause
to variable ratio less than 4.2, the percentage of satisfiable formulas 
increases, and for each clause to variable ratio greater than 4.2, the
percentage of satisfiable formulas decreases as a function of number of
variables.  We found that several algorithms behaved qualitatively in the
same fashion.  We report on the relative performance of each algorithm.
Keywords:  backtracking, logic, reasoning, satisfiability, threshold behavior.


This technical report is available electronically through either 
of the following methods:
1.  through anonymous ftp from ftp.cse.ucsc.edu, in /pub/tr. Log in 
    as "anonymous", use your email address as your password, specify 
    "binary" before getting the file.  Uncompress before printing.
2.  by mail to automatic mail server rnalib@ftp.cse.ucsc.edu.
    Put this command on the subject line or in the body of the message:
	@@ send ucsc-crl-92-42.ps.Z from tr
    To get the index or abstract list:
	@@ send INDEX from tr
	@@ send ABSTRACTS.1992 from tr
    To get the list of the tr directory:
	@@ list tr
    To get the list of commands and their syntax:
	@@ help commands

Order paper copies from:  Technical Library, Baskin Center for Computer 
Engineering & Information Sciences, UCSC, Santa Cruz  CA  95064.
Purchase orders are not accepted.  Checks or money orders must be
for U.S. dollars, payable through a U.S. bank, and made out to 
"UC Regents".

Questions:  jean@cse.ucsc.edu

===========================================================================
Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
	    compdoc-techreports-request@ftp.cse.ucsc.edu