The phase transition in random Horn satisfiability and its algorithmic implications

1999/12/01 by Gabriel Istrate, Istrate, Gabriel
Computer Science · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.3 #I.1.2 #cs.CC #cs.DS #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.cs/9912001

26 pages. Journal version of papers in AIM'98, SODA'99. Submitted to Random Structures and Algorithms

arxiv created 1999/12/01 · openalex publication_date 1999/12/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let c>0 be a constant, and Φ be a random Horn formula with n variables and m=c⋅ 2ⁿ 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 lim_{n\goesto ∞} \PR (Φ is satisfiable)= 1-F(e^-c), where F(x)=(1-x)(1-x²)(1-x⁴)(1-x⁸)... . Our method also yields as a byproduct an average-case analysis of this algorithm.

Related

• On the satisfability of random k-Horn formulae
• A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas
• The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
• The Asymptotic Order of the k-SAT Threshold
• The Threshold for Random k-SAT is 2^k ln2 - O(k)