Publication:4952608
From MaRDI portal
zbMath0959.68135MaRDI QIDQ4952608
Yacine Boufkhad, Olivier Dubois, Jacques Mandler
Publication date: 10 May 2000
68W05: Nonnumerical algorithms
Related Items
Space complexity of random formulae in resolution, On the critical exponents of random k‐SAT, 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 continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas, Rigorous results for random (\(2+p)\)-SAT, Random 2-SAT: Results and problems, Upper bounds on the satisfiability threshold, On the phase transitions of random \(k\)-constraint satisfaction problems, Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT, Estimating satisfiability, On threshold properties of \(k\)-SAT: An additive viewpoint, Regular random \(k\)-SAT: Properties of balanced formulas, On the satisfiability threshold and clustering of solutions of random 3-SAT formulas, The SAT-UNSAT transition for random constraint satisfaction problems, Random constraint satisfaction: easy generation of hard (satisfiable) instances, When does the giant component bring unsatisfiability?, Generalized satisfiability problems: Minimal elements and phase transitions., 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, On the satisfiability threshold of formulas with three literals per clause, Phase transition in a random NK landscape model, A sharp threshold for the renameable-Horn and the \(q\)-Horn properties, Typical case complexity of satisfiability algorithms and the threshold phenomenon, The unsatisfiability threshold revisited, Unnamed Item, The scaling window of the 2-SAT transition, D?E?K=(1000)8, On Random Ordering Constraints, Selecting Complementary Pairs of Literals, An efficient local search method for random 3-satisfiability
