The maximum length of prime implicates for instances of 3-SAT

DOI10.1016/S0004-3702(97)00018-0MaRDI QIDQ1402744zbMATH OpenOpenAlexFDO

Authors Paul E. Dunne, Trevor Bench-Capon

Publication date 28 August 2003

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0004-3702(97)00018-0

zbMATH Keywords

3-CNF formulaePrime implicatesSatisfiability

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Implicates and prime implicates in random 3-SAT
• Length of prime implicants and number of solutions of random CNF formulae
• On Random 3-sat
• A new upper bound for \(( n , 3)\)-MAX-SAT
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A threshold for unsatisfiability
• Implicates and prime implicates in random 3-SAT

Cited in

(2)

• Length of prime implicants and number of solutions of random CNF formulae
• Implicates and prime implicates in random 3-SAT

This page was built for publication: The maximum length of prime implicates for instances of 3-SAT

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