Name
Title | ||
|---|---|---|
Average case results for satisfiability algorithms under the random-clause-width model |
Abstract | ||
|---|---|---|
In the probabilistic analysis of algorithms for the Satisfiability problem, the random‐clause‐width model is one of the most popular for generating random formulas. This model is parameterized and it is not difficult to show that virtually the entire parameter space is covered by a collection of polynomial time algorithms that find solutions to random formulas with probability tending to 1 as formula size increases. But finding a collection of polynomial average time algorithms that cover the parameter space has proved much harder and such results have spanned approximately ten years. However, it can now be said that virtually the entire parameter space is covered by polynomial average time algorithms. This paper relates dominant, exploitable properties of random formulas over the parameter space to mechanisms of polynomial average time algorithms. The probabilistic discussion of such properties is new; main average‐case results over the last ten years are reviewed. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1023/A:1018992730285 | Ann. Math. Artif. Intell. |
Keywords | Field | DocType |
probabilistic analysis,width model,main average,polynomial average time algorithm,random-clause-width model,random formula,average case result,probabilistic discussion,satisfiability algorithm,polynomial time algorithm,Satisfiability problem,entire parameter space,parameter space | Polynomial,Satisfiability,Parameter space,Artificial intelligence,Probabilistic logic,Time complexity,Discrete mathematics,Parameterized complexity,Boolean satisfiability problem,Algorithm,Probabilistic analysis of algorithms,Machine learning,Mathematics | Journal |
Volume | Issue | ISSN |
20 | 1-4 | 1573-7470 |
Citations | PageRank | References |
4 | 0.44 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Franco | 1 | 4 | 0.44 |
| R. P. Swaminathan | 2 | 68 | 5.91 |