Implicates and Prime Implicates in Random 3SAT

It has been observed previously that Random 3SAT exhibits a phase transition at a critical ratio of constraints to variables, where the average frequency of satisfiability falls abruptly from near 1 to near 0. In this paper we look beyond satisfiability to implicates and prime implicates of non-zero length and show experimentally that, for any given length, these exhibit their own phase transitions. All of these phase transitions appear to share the same critical point as the well-known satisfiability phase transition. We also find a rich, regular Some of this work was done while the first author was in the Qualitative Reasoning Group at the Artificial Intelligence Laboratory, the University of Texas at Austin, at a time when the Qualitative Reasoning Group was supported in part by NSF grants IRI-8904454, IRI-9017047, and IRI-9216584, and by NASA contracts NCC 2-760 and NAG 9-665. Some of this work also was done while the first author was at AT&T Bell Laboratories. y The second au..