DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
Relative Size of Certain Polynomial Time Solvable Subclasses of Satisfiability,
CINCINNATI UNIV OH DEPT OF ELECTRICAL AND COMPUTER ENGINEERING
Pagination or Media Count:
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 4kk - 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.
APPROVED FOR PUBLIC RELEASE