+1 vote
24 views

Consider the following Boolean valued function on n Boolean variables: f(x1,…,xn)=x1+⋯+xn(mod 2), where addition is over integers, mapping ‘FALSE’ to 0 and ‘TRUE’ to 1. Consider Boolean circuits (with no feedback) that use only logical AND and OR gates, and where each gate has two input bits, each of which is either an input bit of "f" or the output bit of some other gate of the circuit. The circuit has a distinguished gate whose value is the output of the circuit. The minimum size of such a circuit computing f (asymptotically in n) is :

1. 2^o(logn)
2. n^c, for some fixed constant c
3. n^ω(1), but n^O(logn)
4. 2^Θ(n)
5. None of the others
| 24 views
0
$x_1, x_2, x_3,…,x_n$ are integers, suppose $x_i$ is the largest among these integers, the number of bits it’ll contain will be $\log_2(x_i)$ bits, then the total number of bits for all integers will be $O(n\log_2(x_i))$, now in the worst case all of these bits will be input to 2-input AND/OR gate in the first level, so

$\text{number of gates in the first level = } O(n\log_2(x_i)), \\\text{number of gates in the second level} = \frac{O(n\log_2(x_i))}{2}, \\\text{number of gates in the thirdd level} = \frac{O(n\log_2(x_i))}{2^2},\\…\\\text{number of gates in the final level} = 1 (\text{as mapping is from integers to 0/1})$

$$\text{Total number of gates in all levels} = \log_2(x_i)[n + \frac{n}{2} + \frac{n}{2^2} + \frac{n}{2^3} + … 1] \\= \log_2(x_i)\times(2^{\log_2(n)}-1)$$

Now here, both a and c are possible answers depending on if we consider the value of $x_i$ similar to the constant in non-comparison sorts.