The number of 3-SAT functions

L. Ilinca, J. Kahn

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

With Gk(n) denoting the number of functions of n Boolean variables definable by k-SAT formulas, we prove that G3(n) is asymptotic to. This is a strong form of the case k = 3 of a conjecture of Bollobás, Brightwell and Leader stating that for fixed k.

Original languageEnglish (US)
Pages (from-to)869-919
Number of pages51
JournalIsrael Journal of Mathematics
Volume192
Issue number2
DOIs
StatePublished - Jun 11 2012

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'The number of 3-SAT functions'. Together they form a unique fingerprint.

  • Cite this