A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas

2005/05/02 by Cristopher Moore, Gabriel Istrate, Moore, Cristopher +6
Decision Sciences · Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Mathematics #FOS: Physical sciences #Multi-Criteria Decision Making #Probability (math.PR) #cond-mat.dis-nn #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.math/0505032

arxiv created 2005/05/02 · openalex publication_date 2005/05/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We compute the probability of satisfiability of a class of random Horn-SAT formulae, motivated by a connection with the nonemptiness problem of finite tree automata. In particular, when the maximum clause length is 3, this model displays a curve in its parameter space along which the probability of satisfiability is discontinuous, ending in a second-order phase transition where it becomes continuous. This is the first case in which a phase transition of this type has been rigorously established for a random constraint satisfaction problem.

Related

• The phase transition in random Horn satisfiability and its algorithmic implications
• Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold
• On the satisfability of random k-Horn formulae
• Exact Phase Transitions in Random Constraint Satisfaction Problems
• The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem