Implicates and prime implicates in random 3-SAT

DOI10.1016/0004-3702(95)00053-4MaRDI QIDQ2674186zbMATH OpenOpenAlexWikidataFDO

Authors Robert Schrag, James M. Crawford

Publication date 22 September 2022

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(95)00053-4

zbMATH Keywords

finite-size scalingknowledge compilationminimal nogoodsphase transitionprime implicatespropositional satisfiabilityrandom 3-SATsearch

Mathematics Subject Classification ID

Classical propositional logic (03B05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• The maximum length of prime implicates for instances of 3-SAT
• scientific article; zbMATH DE number 2080304
• Length of prime implicants and number of solutions of random CNF formulae
• Impurity: another phase transition of SAT
• scientific article; zbMATH DE number 2083805

Cites work

• Critical behavior in the computational cost of satisfiability testing
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Experimental results on the crossover point in random 3-SAT
• Exploiting the deep structure of constraint problems
• KI-94: Advances in artificial intelligence. 18th German annual conference on artificial intelligence, Saarbrücken, Germany, September 18-23, 1994. Proceedings
• Many hard examples for resolution
• On the number of prime implicants
• RST Flip-Flop Input Equations
• Synthesizing constraint expressions
• The hardest constraint problems: A double phase transition
• The satisfiability constraint gap

Cited in

(5)

• The maximum length of prime implicates for instances of 3-SAT
• Preprocessing of intractable problems
• Impurity: another phase transition of SAT
• scientific article; zbMATH DE number 2080304 (Why is no real title available?)
• A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses

This page was built for publication: Implicates and prime implicates in random 3-SAT

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