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

Personal Author(s):

• Franco, J.

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.

Descriptors:

• *NONLINEAR PROGRAMMING
• REPRINTS
• SIZES(DIMENSIONS)
• FORMULATIONS
• MATHEMATICAL LOGIC
• SOLUTIONS(GENERAL)
• POLYNOMIALS

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE