
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 kSAT 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, qHorn, extended Horn, CCbalanced, 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