scientific article; zbMATH DE number 1445295
From MaRDI portal
Publication:4952608
zbMath0959.68135MaRDI QIDQ4952608
Yacine Boufkhad, Jacques Mandler, Olivier Dubois
Publication date: 10 May 2000
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (37)
Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT ⋮ A sharp threshold for a random constraint satisfaction problem ⋮ On the critical exponents of random k‐SAT ⋮ On threshold properties of \(k\)-SAT: An additive viewpoint ⋮ The unsatisfiability threshold revisited ⋮ Phase transition in a random NK landscape model ⋮ The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘) ⋮ Regular random \(k\)-SAT: Properties of balanced formulas ⋮ Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability ⋮ Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability ⋮ Unnamed Item ⋮ Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances ⋮ Generalized satisfiability problems: Minimal elements and phase transitions. ⋮ On good algorithms for determining unsatisfiability of propositional formulas ⋮ Fractional Edge Cover Number of Model RB ⋮ The scaling window of the 2-SAT transition ⋮ On the satisfiability threshold and clustering of solutions of random 3-SAT formulas ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ D?E?K=(1000)8 ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT ⋮ A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas ⋮ On the satisfiability threshold of formulas with three literals per clause ⋮ 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 ⋮ Space complexity of random formulae in resolution ⋮ Rigorous results for random (\(2+p)\)-SAT ⋮ Random 2-SAT: Results and problems ⋮ Upper bounds on the satisfiability threshold ⋮ On Random Ordering Constraints ⋮ The SAT-UNSAT transition for random constraint satisfaction problems ⋮ Random constraint satisfaction: easy generation of hard (satisfiable) instances ⋮ Estimating satisfiability ⋮ When does the giant component bring unsatisfiability? ⋮ Speed and concentration of the covering time for structured coupon collectors ⋮ A sharp threshold for the renameable-Horn and the \(q\)-Horn properties ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ Selecting Complementary Pairs of Literals ⋮ An efficient local search method for random 3-satisfiability
This page was built for publication:
