On the occurence of null clauses in random instances of Satisfiability (Q1208481): Difference between revisions

We analyze a popular probabilistic model for generating instances of Satisfiability. According to this model, each of a set \(L=\{v_ 1,\overline v_ 1,v_ 2,\overline v_ 2, \ldots,v_ n,\overline v_ n\}\) of literals appears independently in each of \(m\) clauses with probability \(p\). This model allows null clauses; the frequency of occurrence of such clauses depends on the relationship between the parameters \(n\), \(m\), and \(p\). If an instance contains a null clause it is trivially unsatisfiable. Several papers, for example, by \textit{Iwama}, \textit{Purdom} and \textit{Brown}, present polynomial average time results under this model when null clauses are numerous but, until now, not all such cases have been covered by average-case efficient algorithms. In fact, a recent paper by \textit{Purdom} shows that the average complexity of the pure literal rule is superpolynomial even when most random instances contain a null clause. It is shown in this paper that a simple strategy, based on locating null clauses in a given random input, has polynomial average complexity if either \(m \leq n^{.5}\), and \(pn<\ln(m)/2\); or \(m=n^ \varepsilon\), \(\varepsilon \neq 1\), and \(pn<c (\varepsilon) \ln(m)/2\); or \(m=\beta n\), \(\beta\) a positive constant, and \(2.64(1-e^{-2 \beta pn}(1+2 \beta pn))< \beta e^{-2pn}\). These are essentially the conditions for which null clauses appear in random instances with probability tending to 1. These results are an improvement over some results in the references mentioned above. The strategy is as follows. Search the input for a null clause. If one is found, immediately decide the instance is unsatisfiable. Otherwise, set variables appearing exactly once to satisfy the clauses they occupy and determine satisfiability by exhaustively trying all possible truth assignments to the remaining literals of the input. Because the good average case performance depends completely on the presence of null clauses, we see this work as illuminating properties of the probabilistic model which cause polynomial average time rather than presenting a new algorithm with improved average time behavior.