An Experimental Study of Phase Transitions in Matching

Abstract

Finding models of a predicate logic formula is a well-known hard problem, whose complexity is exponential in the number of variables. However, even though this number is kept constant, substantial differences in complexity arise when searching for solutions in different problem instances. Such a behavior appears to be quite general, according to recent results reported in the literature; in fact, several classes of hard problems exhibit a narrow phase transition with respect to some order parameter, in correspondence of which the complexity dramatically rises up, still r.emaining tractable elsewhere. In this paper we provide an extensive experimental study on the emergence of a phase transition in the problem of matching a Horn clause to a universe, searching for a model of the clause or for a proof that no such model exists. As it turns out, phase transition in the matching problem depends in an essential way on two order parameters, one capturing syntactic aspects of the clause structure (intensional aspect), while the other related to the structure of the universe (extensional aspect).