A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas

DOI10.1002/rsa.20176zbMath1147.68717OpenAlexW2950052714MaRDI QIDQ5433256

Moshe Y. Vardi, Moore, Cristopher, Demetrios D. Demopoulos, Gabriel I. Istrate

Publication date: 8 January 2008

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

Full work available at URL: https://doi.org/10.1002/rsa.20176

zbMATH Keywords

phase transitionsdifferential equationsstatistical physicssatisfiability

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (2)

Copy complexity of Horn formulas with respect to unit read-once resolution ⋮ Combinatorial Problems for Horn Clauses

Cites Work

• Automata-theoretic techniques for modal logics of programs
• Selecting Complementary Pairs of Literals
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas