Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
From MaRDI portal
Publication:918700
DOI10.1016/0020-0255(90)90030-EzbMath0706.68053OpenAlexW2054387247MaRDI QIDQ918700
Publication date: 1990
Published in: Information Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0255(90)90030-e
Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Parallel algorithms in computer science (68W10)
Related Items (30)
Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas ⋮ A sharp threshold for a random constraint satisfaction problem ⋮ An improved upper bound on the non-3-colourability threshold ⋮ A sharp threshold in proof complexity yields lower bounds for satisfiability search ⋮ An algorithm for random signed 3-SAT with intervals ⋮ The expected complexity of analytic tableaux analyses in propositional calculus. II ⋮ Phase transition in a random NK landscape model ⋮ The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘) ⋮ Probabilistic performance of a heurisic for the satisfiability problem ⋮ Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances ⋮ Phase transitions and the search problem ⋮ Some pitfalls for experimenters with random SAT ⋮ On good algorithms for determining unsatisfiability of propositional formulas ⋮ The scaling window of the 2-SAT transition ⋮ A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses ⋮ Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT ⋮ Statistical mechanics methods and phase transitions in optimization problems ⋮ Rigorous results for random (\(2+p)\)-SAT ⋮ Lower bounds for random 3-SAT via differential equations ⋮ Upper bounds on the satisfiability threshold ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Super solutions of random \((3 + p)\)-SAT ⋮ On Super Strong ETH ⋮ Hard satisfiable instances for DPLL-type algorithms ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem ⋮ Selecting Complementary Pairs of Literals ⋮ A perspective on certain polynomial-time solvable classes of satisfiability ⋮ Walksat Stalls Well Below Satisfiability ⋮ Solving non-uniform planted and filtered random SAT formulas greedily
Cites Work
- Unnamed Item
- Average time analyses of simplified Davis-Putnam procedures
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- The Pure Literal Rule and Polynomial Average Time
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- An Average Time Analysis of Backtracking
- A Computing Procedure for Quantification Theory
This page was built for publication: Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
