Length of prime implicants and number of solutions of random CNF formulae

DOI10.1016/S0304-3975(95)00184-0zbMath0913.68069MaRDI QIDQ1285568

Olivier Dubois, Yacine Boufkhad

Publication date: 28 April 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

number of solutionssatisfiabilityprime implicantsDavis and Putnam

Mathematics Subject Classification ID

Related Items (6)

An efficient approach to solving random \(k\)-SAT problems ⋮ The number of satisfying assignments of random 2‐SAT formulas ⋮ Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities ⋮ Statistical mechanics methods and phase transitions in optimization problems ⋮ Random 2-SAT: Results and problems ⋮ Upper bounds on the satisfiability threshold

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic Estimates of Stirling Numbers
• A Way to Simplify Truth Functions
• On some generalized farlie-gumbel-morgenstern distributions-II regression, correlation and further generalizations
• Sharp thresholds of graph properties, and the $k$-sat problem
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• A threshold for unsatisfiability
• On Cores and Prime Implicants of Truth Functions
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• The Problem of Simplifying Truth Functions

This page was built for publication: Length of prime implicants and number of solutions of random CNF formulae