Given a Boolean function that can be expressed using universal logic gates (e.g. NAND), has $n$ inputs, and has a single output, what is the most efficient algorithm that can compute the probability of the output being a $1$ for a random combination of inputs?

A naive approach would be to test all possible inputs, count the number of times a $1$ is produced as output, and divide that total by $2^n$. However, one can clearly see this has a time complexity of $O(2^n)$, so is there an algorithm more efficient than this?

An efficient yet incorrect approach would be to treat all variables as having a probability of $\frac{1}{2}$ and compute the outputs of logic functions in terms of these probabilities. For instance, if the function was $(a \wedge b) \wedge c $, then $\frac{1}{2} \wedge \frac{1}{2}$ would equal $\frac{1}{4}$ and $\frac{1}{4} \wedge \frac{1}{2}$ would equal $\frac{1}{8}$. However, this will fail when an input is used multiple times in the function, such as in $(a \wedge b) \wedge a$, which has a probability of $\frac{1}{2}$.

  • 3
    $\begingroup$ The zero-vs-nonzero problem is equivalent to Circuit-SAT, so there are no known exact algorithms substantially faster than the brute force approach you mentioned. (Additive) approximations can be attained by random sampling. Deterministic approaches to the approximation problem are famously very elusive. $\endgroup$ – Yonatan N Oct 21 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.