2
$\begingroup$

Given a randomly generated AND/OR tree (and negations), we can calculate the probability that the circuit will represent a specific Boolean function up to 3 input literals. Starting from 4 (or at least 5) literals, the system of equations becomes too complex to compute, and it's even questionable whether the output distribution of Boolean functions can be reliably approximated. See D. Gardy, Random Boolean Expressions, chapter 3.4.3.

Another line of research deals with the question of how robust Boolean circuits are in the presence of noise or faulty gates. See P. Gács, A. Gál, Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates and A. Mozeika, D. Saad, On reliable computation by noisy random Boolean formulas who explicitly consider random Boolean formulas.

My question is if there is correlation between the probability/frequency of a certain Boolean function and the resilience of a given generating circuit (formula) against noise. In other words, can we estimate (or at least get some bounds on) the probability of a function from the circuit's noise resilience which we could try to measure by causing arbitrary perturbations to gates and see how the resulting function reacts?

My intuition is that circuits representing simple Boolean functions with high probability such as the tautology TRUE or the output of a single literal will tolerate higher noise levels since those circuits have a higher "density" in the space of all possible circuits of a given size.

Improve this question
$\endgroup$
1
  • $\begingroup$ I'd think that such resilience depends not only on how many Boolean ckts compute the same functions, but how closely related those circuits are to one another. Put another way: for a given function, if we look at all the ckts computing it, where do they sit relative to one another in the space of all ckts? For tautologies, you might consider minimal DNF tautologies - ones in which the removal of any single clause makes it not a tautology. Then it's not robust to the removal of one clause, but once you remove say 1% of clauses, you can ask if it's now robust. $\endgroup$
    – Joshua Grochow
    Sep 11, 2019 at 20:20

1 Answer 1

Reset to default
1
$\begingroup$

I have found some hints on my question in Moshe Looks, Competent Program Evolution, p. 31:

Most local perturbations of large random formulae have no effect – 96% of them for arity five, and 91% for arity ten (the drop is a corollary of the increase in the percentage of unique behaviors in a fixed size sample as the arity increase). This is a consequence of such formulae typically being highly redundant – e.g., a large formula that computes a tautology will likely remain a tautology when randomly perturbed (similarly a large subformula which computes a tautology, etc.).

More resources would be highly appreciated if you know of any.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.