retagged by
659 views
1 votes
1 votes

Consider the following Boolean valued function on $n$ Boolean variables: $f(x_{1},\dots,x_{n}) = x_{1} + \dots + x_{n}(\text{mod } 2)$, where addition is over integers, mapping $\textbf{‘FALSE’}$ to $0$ and $\textbf{‘TRUE’}$ to $1.$ Consider Boolean circuits (with no feedback) that use only logical $\textbf{AND}$ and $\textbf{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(\log n)}$
  2. $n^{c}$, for some fixed constant $c$
  3. $n^{\omega(1)}$, but $n^{O(\log n)}$
  4. $2^{\Theta(n)}$
  5. None of the others
retagged by

Please log in or register to answer this question.

Answer:

Related questions

3 votes
3 votes
1 answer
1
6 votes
6 votes
1 answer
2
9 votes
9 votes
4 answers
3
admin asked Feb 10, 2020
4,584 views
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of $n$) asymptotically?$2^{\log n}$$n^{10}$$(\sqrt{\log n})^{\log ^{...