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

DOI10.1002/RSA.20176MaRDI QIDQ5433256zbMATH OpenOpenAlexFDO

Authors Cristopher Moore, Demetrios D. Demopoulos, Moshe Y. Vardi, Gabriel 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

differential equationsphase transitionssatisfiabilitystatistical physics

Mathematics Subject Classification ID

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

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 1305521
• The phase transition in random horn satisfiability and its algorithmic implications
• The SAT-UNSAT transition for random constraint satisfaction problems
• scientific article; zbMATH DE number 2151254
• scientific article; zbMATH DE number 2127760
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• The satisfiability threshold for non-uniform random 2-SAT
• Approximating the unsatisfiability threshold of random formulas (extended abstract)

Cites work

• Automata-theoretic techniques for modal logics of programs
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1948386 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• Selecting Complementary Pairs of Literals
• The phase transition in 1-in-k SAT and NAE 3-SAT

Cited in

(4)

• Copy complexity of Horn formulas with respect to unit read-once resolution
• Combinatorial Problems for Horn Clauses
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Kernelization, proof complexity and social choice

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

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