On the occurence of null clauses in random instances of Satisfiability (Q1208481): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q673601 |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: John V. Franco / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast probabilistic algorithms for Hamiltonian circuits and matchings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Exponential Average Time for the Pure Literal Rule / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Pure Literal Rule and Polynomial Average Time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Polynomial-average-time satisfiability problems / rank | |||
Normal rank |
Latest revision as of 16:25, 17 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the occurence of null clauses in random instances of Satisfiability |
scientific article |
Statements
On the occurence of null clauses in random instances of Satisfiability (English)
0 references
16 May 1993
0 references
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.
0 references
satisfiability
0 references
probabilistic model
0 references
0 references