Relative Size of Certain Polynomial Time Solvable Subclasses of Satisfiability,

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1997
Accession Number
ADA326040

Entities

People

  • J. Franco

Organizations

  • University of Cincinnati

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computer Science
  • Decomposition
  • Hierarchies
  • Inequalities
  • Linear Programming
  • Mathematics
  • Military Research
  • Operations Research
  • Polynomials
  • Probability
  • Probability Distributions
  • Sequences
  • Structural Properties
  • Theoretical Computer Science

Fields of Study

  • Mathematics

Readers

  • Fault Tolerant Diagnosis of Black and White Balloon Isolation Tests Using ¥.
  • Mathematical Modeling and Probability Theory.