Universität zu Köln

Wotzlaw, Andreas, Speckenmeyer, Ewald and Porschen, Stefan (2012). Probabilistic Analysis of Random Mixed Horn Formulas. Working Paper.

Preview

PDF sat2012.pdf Download (289kB) | Preview

Abstract

We present a probabilistic analysis of random mixed Horn formulas (MHF), i.e., formulas in conjunctive normal form consisting of a positive monotone part of quadratic clauses and a part of Horn clauses, with m clauses, n variables, and up to n literals per Horn clause. For MHFs parameterized by n and m with uniform distribution of instances and for large n, we derive upper bounds for the expected number of models. For the class of random negative MHFs, where only monotone negative Horn clauses are allowed to occur, we give a lower bound for the probability that formulas from this class are satisfiable. We expect that the model studied theoretically here may be of interest for the determination of hard instances, which are conjectured to be found in the transition area from satisfiability to unsatisfiability of the instances from the parameterized classes of formulas.

Item Type:	Preprints, Working Papers or Reports (Working Paper)
Creators:	Creators Email ORCID ORCID Put Code Wotzlaw, Andreas UNSPECIFIED UNSPECIFIED UNSPECIFIED Speckenmeyer, Ewald UNSPECIFIED UNSPECIFIED UNSPECIFIED Porschen, Stefan UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-550272
Date:	February 2012
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/55027