The phase transition in random horn satisfiability and its algorithmic implications

DOI10.1002/rsa.10028zbMath1066.68054arXivcs/9912001OpenAlexW2031284352MaRDI QIDQ4543632

Gabriel I. Istrate

Publication date: 8 August 2002

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/9912001

zbMATH Keywords

phase transitionrandom Horn satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Threshold properties of random Boolean constraint satisfaction problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On finding solutions for extended Horn formulas
• A threshold for unsatisfiability
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Unit Refutations and Horn Sets
• Extended Horn sets in propositional logic
• Reasoning about temporal relations
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• The complexity of satisfiability problems