3
$\begingroup$

Given a bunch of boolean variables $a_i \in \{0, 1\}$, I want to write a boolean formula to express $\sum_{i=1}^n a_i \geq k$.

i.e. I'm allowed to use $(, ), \wedge, \vee, \lnot$.

Now, if I allow the use of $\exist$, then I can do this as a formular of length O(n^c) (basically create a circuit that adds together the $a_i$ and does a comparison against $k$, then use the existential quantifier to create variables representing the intermediate nodes of the circuit).

However, if I am not allowed to use the existential quantifier, and I can not create intermediate nodes, can I do this in a formula of sub exponential length?

Thanks!

$\endgroup$
1
  • 3
    $\begingroup$ I think you'll have better luck with this question at stackexchange. $\endgroup$ Commented Jun 5, 2011 at 11:04

1 Answer 1

6
$\begingroup$

Yes, there exist (uniformly constructible) polynomial-size Boolean formulas for threshold functions (which is how your functions are called). Equivalently, there are polynomial-size formulas for summing $n$ binary numbers of length $m$. Also equivalently, the complexity class (uniform) $\mathrm{TC}^0$ is contained in (uniform) $\mathrm{NC}^1$.

The easy way to do it is to use the so-called carry-save addition. This is a recursive construction whose basic step is a reduction of the computation of a sum of $3$ numbers $a,b,c$ to a sum of $2$ numbers $d,e$ using a linear-size constant-depth fan-in $2$ circuit (or formula): $d$ consists of bitwise sums of the inputs modulo $2$ disregarding any carries (i.e., the $i$th bit $d_i$ is $a_i\oplus b_i\oplus c_i$, where $\oplus$ denotes the parity function), whereas $e$ is the carry vector ($e_{i+1}=1$ iff $a_i+b_i+c_i\ge2$). By taking $n/3$ of these basic blocks in parallel, we can reduce a sum of $n$ numbers to a sum of $2n/3$ numbers by a constant-depth circuit, and by repeating this step $\log_{3/2}n$ times, we can sum $n$ numbers by a circuit of depth $O(\log n)$. Since a circuit of depth $d$ and fan-in $2$ with $k$ output bits can be expanded to a formula of size $k2^d$, this gives formulas of size $n^{O(1)}$.

In fact, threshold functions are also computable by polynomial-size log-depth monotone formulas (i.e., using only $\land$ and $\lor$, but not $\neg$), but this is harder to prove. A simple but nonconstructive probabilistic proof of the existence of such formulas was given by Valiant (Short monotone formulae for the majority function, J. of Algorithms 5 (1983), #3, 363–366). A constructive but very complicated construction follows from the construction of log-depth sorting networks by Ajtai, Komlós and Szemerédi (An $O(n\log n)$ sorting network, Proc. 15th STOC, 1983, 1–9).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .