Quick links

Probabilistic Spaces of Boolean Functions of a Given Complexity: Generalities and Random $k$-SAT Coefficients

Report ID:
June 1992
Download Formats:


In this paper we develop an approach to studying probabilistic spaces
of boolean functions, namely recovering exact formulas for the event
probabilities in terms of the moments. While this involves analyzing
a large number of moments, there are situations in which this seems
feasible to do; for the $m$-fold AND of a probability space of
functions, there is a formula involving coefficients with a geometric
intepretation (and which is otherwise quite simple). We investigate
the coefficients involved in the $k$-SAT problem, where we give a
formula for the $1$-SAT coefficients and are able to understand a few
of the $2$-SAT coefficients.

Follow us: Facebook Twitter Linkedin