Universität zu Köln

Speckenmeyer, Ewald, Böhm, Max and Heusch, Peter (1997). On the Imbalance of Distributions of Solutions of CNF-Formulas and its Impact on Satisfiability Solvers. Providence, RI: American Math. Soc.. ['eprint_fieldopt_monograph_type_preprint' not defined].

Preview

PDF zpr96-235.pdf - Submitted Version Download (179kB) | Preview

Abstract

Let F be Boolean formulas in conjunctive normal form with n variables, r clauses, every clause has length s. We show that if F is split into two subformulas F_{v} and F_{overline{v}} by setting v true and false in F, then the expected number of solutions of one of the two subformulas F_{v} and F_{overline{v}} is significantly higher than that in the other subformula, when dealing with classes of formulas where the great majority of formulas is satisfiable. We discuss practical consequences of this result.

Item Type:	Monograph (['eprint_fieldopt_monograph_type_preprint' not defined])
Creators:	Creators Email ORCID ORCID Put Code Speckenmeyer, Ewald UNSPECIFIED UNSPECIFIED UNSPECIFIED Böhm, Max UNSPECIFIED UNSPECIFIED UNSPECIFIED Heusch, Peter UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-547574
Series Name:	DIMACS series in discrete mathematics and theoretical computer science
Volume:	35
Page Range:	pp. 669-676
Date:	1997
Publisher:	American Math. Soc.
Place of Publication:	Providence, RI
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54757