2
votes
Accepted
Complexity of a Set of Formulas
Yes. You can build a Boolean circuit $\beta_n$ of size $O(n \lg n)$, that is equivalent to $\alpha_n$. It works by counting the number of "true"s among the inputs, compares it to $n$, and ...
D.W.♦
- 154k
Only top scored, non community-wiki answers of a minimum length are eligible