The phase transition in random horn satisfiability and its algorithmic implications

DOI10.1002/RSA.10028MaRDI QIDQ4543632zbMATH OpenOpenAlexFDO

Authors Gabriel Istrate

Publication date 8 August 2002

Published in Random Structures \& 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)

Abstract: Let c>0 be a constant, and $Phi$ be a random Horn formula with n variables and $m=ccdot{2}^n$ clauses, chosen uniformly at random (with repetition) from the set of all nonempty Horn clauses in the given variables. By analyzing PUR, a natural implementation of positive unit resolution, we show that $$Phi$$, where $F(x)=(1-x)(1-x^2)(1-x^4)(1-x^8)\mathrm{...}$. Our method also yields as a byproduct an average-case analysis of this algorithm.

Recommendations

• scientific article; zbMATH DE number 1305521
• scientific article; zbMATH DE number 2151254
• A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
• Probabilistic performance of a heurisic for the satisfiability problem
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

Cites work

• A threshold for unsatisfiability
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Extended Horn sets in propositional logic
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• scientific article; zbMATH DE number 1305521 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1369843 (Why is no real title available?)
• scientific article; zbMATH DE number 837692 (Why is no real title available?)
• scientific article; zbMATH DE number 850067 (Why is no real title available?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• On finding solutions for extended Horn formulas
• Reasoning about temporal relations
• The complexity of satisfiability problems
• Unit Refutations and Horn Sets

Cited in

(8)

• Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
• Threshold properties of random Boolean constraint satisfaction problems
• scientific article; zbMATH DE number 5547881 (Why is no real title available?)
• scientific article; zbMATH DE number 1305521 (Why is no real title available?)
• scientific article; zbMATH DE number 2151254 (Why is no real title available?)
• A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses

This page was built for publication: The phase transition in random horn satisfiability and its algorithmic implications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4543632)