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

DOI10.1016/S0004-3702(97)00018-0zbMath1017.68512OpenAlexW2092428555MaRDI QIDQ1402744

Trevor J. M. Bench-Capon, Paul E. Dunne

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

Satisfiability3-CNF formulaePrime implicates

Mathematics Subject Classification ID

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

Cites Work

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

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