Theory and Applications of Satisfiability Testing

DOI10.1007/B95238zbMATH Open1204.68214DBLPconf/sat/2003OpenAlexW2494235144MaRDI QIDQ5325856FDOQ5325856

Linda van Norden, Hans van Maaren

Publication date: 24 July 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b95238

Recommendations

• scientific article; zbMATH DE number 1305521
• A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• scientific article; zbMATH DE number 2083805
• The 3-XORSAT threshold.

zbMATH Keywords

thresholdssatisfiability3-SATHorngraph-3-coloring

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Coloring of graphs and hypergraphs (05C15)

Cited In (5)

• Satisfiability of mixed Horn formulas
• Copy complexity of Horn formulas with respect to unit read-once resolution
• Results related to threshold phenomena research in satisfiability: Lower bounds
• Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances
• On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls

This page was built for publication: Theory and Applications of Satisfiability Testing

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