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