Analysis of Two Simple Heuristics on a Random Instance ofk-sat
From MaRDI portal
Publication:4876696
DOI10.1006/jagm.1996.0016zbMath0852.68038OpenAlexW2051580875WikidataQ57401560 ScholiaQ57401560MaRDI QIDQ4876696
Publication date: 6 May 1996
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1996.0016
Related Items
Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas, A sharp threshold for a random constraint satisfaction problem, Waiter-client and client-waiter colourability and \(k\)-SAT games, Deep learning: a statistical viewpoint, Sharp thresholds of graph properties, and the $k$-sat problem, On the solution‐space geometry of random constraint satisfaction problems, A sharp threshold in proof complexity yields lower bounds for satisfiability search, On independent sets in random graphs, The phase transition in random horn satisfiability and its algorithmic implications, An algorithm for random signed 3-SAT with intervals, On threshold properties of \(k\)-SAT: An additive viewpoint, The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘), Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability, Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability, A general model and thresholds for random constraint satisfaction problems, Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances, Unnamed Item, A fast parallel SAT-solver -- efficient workload balancing, Maximum independent sets on random regular graphs, On the thresholds in linear and nonlinear Boolean equations, The asymptotic \(k\)-SAT threshold, On good algorithms for determining unsatisfiability of propositional formulas, Satisfiability threshold for random XOR-CNF formulas, The cook-book approach to the differential equation method, Phase transitions of contingent planning problem, The scaling window of the 2-SAT transition, The Decimation Process in Random k-SAT, Finite size scaling for the core of large random hypergraphs, A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses, 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, Bounding the scaling window of random constraint satisfaction problems, 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, A perspective on certain polynomial-time solvable classes of satisfiability
