A sharp threshold for the renameable-Horn and the q-Horn properties

DOI10.1016/J.DAM.2005.05.005MaRDI QIDQ2581546zbMATH OpenOpenAlexFDO

Authors Nadia Creignou, Hervé Daudé, John V. Franco

Publication date 10 January 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.05.005

zbMATH Keywords

\(q\)-Hornrandom formularenameable-Hornsharp satisfiability threshold

Mathematics Subject Classification ID

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

Recommendations

• The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
• scientific article; zbMATH DE number 5244891
• A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
• New combinatorial topology upper and lower bounds for renaming
• Unique Horn renaming and Unique 2-Satisfiability
• On the size of maximum renamable Horn sub-CNF
• New combinatorial topology bounds for renaming: the lower bound
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• On renaming a set of clauses as a Horn set
• New combinatorial topology bounds for renaming: the upper bound

Cites work

• scientific article; zbMATH DE number 437557 (Why is no real title available?)
• 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 1947423 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• A Complexity Index for Satisfiability Problems
• A linear algorithm for renaming a set of clauses as a Horn set
• A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
• A perspective on certain polynomial-time solvable classes of satisfiability
• A threshold for unsatisfiability
• Approximation algorithms for combinatorial problems
• Bounded model checking using satisfiability solving
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Determining computational complexity from characteristic ``phase transitions
• Extended Horn sets in propositional logic
• Generalized satisfiability problems: Minimal elements and phase transitions.
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Models for Random Constraint Satisfaction Problems
• On finding solutions for extended Horn formulas
• Recognition of q-Horn formulae in linear time
• Renaming a Set of Clauses as a Horn Set
• Sharp thresholds for certain Ramsey properties of random graphs
• Sharp thresholds of graph properties, and the $k$-sat problem
• Statistical mechanics methods and phase transitions in optimization problems
• Supersaturated graphs and hypergraphs

Cited in

(4)

• The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
• scientific article; zbMATH DE number 2151254 (Why is no real title available?)
• A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
• The SAT-UNSAT transition for random constraint satisfaction problems

This page was built for publication: A sharp threshold for the renameable-Horn and the \(q\)-Horn properties

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