Accession Number : ADA326040
Title : Relative Size of Certain Polynomial Time Solvable Subclasses of Satisfiability,
Corporate Author : CINCINNATI UNIV OH DEPT OF ELECTRICAL AND COMPUTER ENGINEERING
Personal Author(s) : Franco, J.
PDF Url : ADA326040
Report Date : 1997
Pagination or Media Count : 13
Abstract : We determine, according to a certain measure, the relative sizes of several well known polynomially solvable subclasses of SAT. The measure we adopt is the probability that randomly selected k-SAT formulas belong to the subclass of formulas in question. This probability is a function of the ratio r of clauses to variables and we determine those ranges of this ratio that result in membership with high probability. We show, for any fixed r > 4/(k(k - 1)), the probability that a random formula is SLUR, q-Horn, extended Horn, CC-balanced, or renamable Horn tends to 0 as n approaches infinity. We also show that most random unsatisfiable formulas are not members of one of these subclasses.
Descriptors : *NONLINEAR PROGRAMMING, REPRINTS, SIZES(DIMENSIONS), FORMULATIONS, MATHEMATICAL LOGIC, SOLUTIONS(GENERAL), POLYNOMIALS.
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE