A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
From MaRDI portal
Publication:2581546
DOI10.1016/j.dam.2005.05.005zbMath1105.68096OpenAlexW2001835703MaRDI QIDQ2581546
Hervé Daudé, Nadia Creignou, John V. Franco
Publication date: 10 January 2006
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.005
Related Items
The SAT-UNSAT transition for random constraint satisfaction problems ⋮ The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combinatorial sharpness criterion and phase transition classification for random CSPs
- On finding solutions for extended Horn formulas
- A threshold for unsatisfiability
- Supersaturated graphs and hypergraphs
- Approximation algorithms for combinatorial problems
- A linear algorithm for renaming a set of clauses as a Horn set
- Recognition of \(q\)-Horn formulae in linear time
- Generalized satisfiability problems: Minimal elements and phase transitions.
- A perspective on certain polynomial-time solvable classes of satisfiability
- A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Renaming a Set of Clauses as a Horn Set
- Sharp thresholds of graph properties, and the $k$-sat problem
- A Complexity Index for Satisfiability Problems
- Extended Horn sets in propositional logic
- Sharp thresholds for certain Ramsey properties of random graphs
- Models for Random Constraint Satisfaction Problems
- Determining computational complexity from characteristic ‘phase transitions’
- Bounded model checking using satisfiability solving
- Statistical mechanics methods and phase transitions in optimization problems
