Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem

Recommendations

Probabilistic performance of a heurisic for the satisfiability problem
Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
scientific article; zbMATH DE number 4102824
The probabilistic analysis of a greedy satisfiability algorithm
An exact and a randomized approach for the satisfiability problem

Cited in

(40)

Probabilistic performance of a heurisic for the satisfiability problem
An efficient algorithm for the 3-satisfiability problem
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.
On good algorithms for determining unsatisfiability of propositional formulas
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
A sharp threshold for a random constraint satisfaction problem
Belief propagation on the random \(k\)-SAT model
Solving non-uniform planted and filtered random SAT formulas greedily
Super solutions of random \((3 + p)\)-SAT
Phase transition in a random NK landscape model
Typical case complexity of satisfiability algorithms and the threshold phenomenon
An algorithm for random signed 3-SAT with intervals
Phase transitions of PP-complete satisfiability problems
The scaling window of the 2-SAT transition
Statistical physics analysis of the backtrack resolution of random 3-SAT instances
An exact and a randomized approach for the satisfiability problem
Random k-SAT and the power of two choices
Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
Selecting Complementary Pairs of Literals
Application of soil-structure interaction to off-shore foundations with specific reference to consolidation analysis
scientific article; zbMATH DE number 4102824 (Why is no real title available?)
Sharp thresholds of graph properties, and the k-sat problem
The cook-book approach to the differential equation method
On Random 3-sat
Analysis of Two Simple Heuristics on a Random Instance ofk-sat
A threshold for unsatisfiability
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
Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
Biased random k‐SAT
On the thresholds in linear and nonlinear Boolean equations
Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
A comparative runtime analysis of heuristic algorithms for satisfiability problems
Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
Probabilistic bounds and algorithms for the maximum satisfiability problem
Solution clustering in random satisfiability

This page was built for publication: Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3758242)