scientific article; zbMATH DE number 1445295
From MaRDI portal
Publication:4952608
Recommendations
- Bounding the unsatisfiability threshold of random 3-SAT
- Approximating the unsatisfiability threshold of random formulas (extended abstract)
- Approximating the unsatisfiability threshold of random formulas
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
Cited in
(45)- 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
- Random 3-SAT: The plot thickens
- 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
- The scaling window of the 2-SAT transition
- The unsatisfiability threshold revisited
- D E K=(100)_8
- scientific article; zbMATH DE number 437557 (Why is no real title available?)
- On Random Ordering Constraints
- Selecting Complementary Pairs of Literals
- An efficient local search method for random 3-satisfiability
- Space complexity of random formulae in resolution
- Bounding the unsatisfiability threshold of random 3-SAT
- Fractional edge cover number of Model RB
- 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
- Tricritical points in random combinatorics: the -SAT case
- Speed and concentration of the covering time for structured coupon collectors
- Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
- Computer Science Logic
- A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas
- On the phase transitions of random \(k\)-constraint satisfaction problems
- Rigorous results for random (2+p)-SAT
- Random 2-SAT: Results and problems
- Upper bounds on the satisfiability threshold
- Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
- Polarised random k-SAT
- Faster random k-CNF satisfiability
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
- On the satisfiability of random 3-SAT formulas with \(k\)-wise independent clauses
- 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
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4952608)
