Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
From MaRDI portal
Publication:3758242
DOI10.1137/0215080zbMath0621.68031OpenAlexW2164346692MaRDI QIDQ3758242
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/305e2f8b6d156d3f8b6c1faab10f8f3e489ac6d6
Related Items
A sharp threshold for a random constraint satisfaction problem, Sharp thresholds of graph properties, and the $k$-sat problem, An algorithm for random signed 3-SAT with intervals, Exact satisfiability, a natural extension of set partition, and its average case behavior, An average case analysis of a resolution principle algorithm in mechanical theorem proving., Performances of pure random walk algorithms on constraint satisfaction problems with growing domains, Phase transitions of PP-complete satisfiability problems, Phase transition in a random NK landscape model, Random k -SAT and the power of two choices, Probabilistic performance of a heurisic for the satisfiability problem, Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances, Application of soil-structure interaction to off-shore foundations with specific reference to consolidation analysis, On the thresholds in linear and nonlinear Boolean equations, Biased random k‐SAT, On Random 3-sat, On good algorithms for determining unsatisfiability of propositional formulas, Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem, The cook-book approach to the differential equation method, The scaling window of the 2-SAT transition, Solution clustering in random satisfiability, 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, Rigorous results for random (\(2+p)\)-SAT, Random 2-SAT: Results and problems, Results related to threshold phenomena research in satisfiability: Lower bounds, Lower bounds for random 3-SAT via differential equations, Upper bounds on the satisfiability threshold, A threshold for unsatisfiability, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, Super solutions of random \((3 + p)\)-SAT, Belief propagation on the random \(k\)-SAT model, Typical case complexity of satisfiability algorithms and the threshold phenomenon, Selecting Complementary Pairs of Literals, Solving non-uniform planted and filtered random SAT formulas greedily
