Relative Size of Certain Polynomial Time Solvable Subclasses of Satisfiability

摘要

We determine, according to a certain measure, the relative sizes of several wellknown 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