PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
The first observation is that the circuit is monotone. Specifically, let x,y be two input bit strings satisfying x_i <= y_i for each bit (thinking of false as 0 and true as 1). Then, c(x) <= c(y) for functions involving only AND and OR gates where c(z) is the output bit of the circuit given bit string z. We say the circuit is monotone in this case.
Let f(p) denote the probability the circuit outputs 1 if each input bit of the circuit is selected to be 1 independently at random with probability p in [0,1]. It is intuitively true that when f is monotone then f(p) is an increasing function of p (the proof is deferred to the last paragraph). Also, given a value p, we have an efficient algorithm to compute f(p) in the following manner. Let g(v,p) denote the probability that node v is 1 if the inputs are independently and randomly set to 1 with probability p. Note, f(p) = g(v,p) when v is the output node. Also, saying that flipping a bit affects at most one input to each gate is the same as saying the events of the inputs to a gate being 0 or 1 are independent (i.e. the different input lines to a gate don’t ultimately depend on any common variable). Thus, g(v,p) is described by the following recurrence
g(v,p) = p if v is an input node
g(v,p) = 1-(1-g(a,p)) * (1-g(b,p)) if v is an OR gate with input nodes a and b (1 minus the probability both inputs are zero).
g(v,p) = g(a,p) * g(b,p) if v is an AND gate with input nodes a and b
In the case of the circuits in the problem we have f(0) = 0 and f(1) = 1. The above recurrence shows f(p) is also a polynomial in p so f(p) increases from 0 to 1 as p increases from 0 to 1. Now, given the algorithm to compute g(v,p) and the fact that f(p) is increasing, we may binary search for the value p (or at least within a small epsilon of p) such that f(p) = 1/2. The complexity is O(n * binary_search_queries) where the n comes from evaluating f(p). Since this problem requires only a fixed amount of precision, the number of binary search queries can essentially be regarded as a constant.
To prove each g(v,p) is an increasing function of p we note that the recurrence easily shows (i.e. an easy proof by induction on the depth) that g(v,p) is a non-constant polynomial satisfying g(v,0) = 0 and g(v,1) = 1. Furthermore, we have 0 < g(v,p) < 1 for 0 < p < 1 since the circuit is non-constant so inputs causing node v to output either 0 or 1 happen with positive probability for any 0 < p < 1. Finally, we prove 0 < g’(v,p) (the derivative with respect to p) for p in (0,1) by induction on the depth. The base case is when v is an input node, in which case g’(v,p) = 1. Otherwise, if v is an AND gate then g’(v,p) = g(a,p)*g’(b,p) + g’(a,p) * g(b,p). All four terms are positive (by induction) so g’(v,p) > 0. A similar argument works for v being an OR gate (it is here where we require g(v,p) < 1 for p < 1). Thus, g(v,p) is strictly increasing as p ranges from 0 to 1.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.