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.

# Accession Number:

## ADA326040

# Title:

## Relative Size of Certain Polynomial Time Solvable Subclasses of Satisfiability,

# Descriptive Note:

# Corporate Author:

## CINCINNATI UNIV OH DEPT OF ELECTRICAL AND COMPUTER ENGINEERING

# Report Date:

## 1997-01-01

# Pagination or Media Count:

##
13.0

# 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 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.

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#