|
TR-387-92
Probabilistic Spaces of Boolean Functions of a Given Complexity: Generalities and Random $k$-SAT Coefficients |
|
| Authors: | Friedman, Joel |
| Date: | July 1992 |
| Pages: | 28 |
| Download Formats: | [PDF] |
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. |
|