THE MAXIMUM LENGTH OF PRIME IMPLICATES FOR INSTANCES OF 3-SAT

Schrag and Crawford (1996) present strong experimental evidence that t he occurrence of prime implicates of varying lengths in random instanc es of 3-SAT exhibits behaviour similar to the well known phase transit ion phenomenon associated with satisfiability. Thus, as the ratio of n umber of clauses (m) to number of propositional variables (n) increase s, random instances of 3-SAT progress from formulae which are generall y satisfiable through to formulae which are generally not satisfiable, with an apparent sharp threshold being crossed when m/n similar to 4. 2. For instances of 3-SAT, Schrag and Crawford (1996) examine with wha t probability the longest prime implicate has length k (for k greater than or equal to 0)-unsatisfiable formulae correspond to those having only a prime implicate of length 0-demonstrating that similar behaviou r arises. It is observed by Schrag and Crawford (1996) that experiment s failed to identify any instance of 3-SAT over nine propositional var iables having a prime implicate of length 7 or greater, and it is conj ectured that no such instances are possible, In this note we present a combinatorial argument establishing that no 3-SAT instance on n varia bles can have a prime implicate whose length exceeds max{inverted righ t perpendicularn/2inverted left perpendicular + right perpendicular 2n /3left perpendicular}, validating this conjecture for the case n = 9. We further show that these bounds are the best possible. An easy corol lary of the latter constructions is that for all k > 3, instances of k -SAT on n variables can be formed, that have prime implicates of lengt h n - o(n). (C) 1997 Elsevier Science B.V.