8
$\begingroup$

Say you have $m$ boolean inputs, and you are given a threshold $n$. You need to construct a boolean circuit that evaluates to true if at least $n$ of the inputs true. You may use AND, OR, NOT, or XOR gates (restricted to fan-in two, with arbitrary fan-out). Asymptotically how small can you make this circuit?

Any reasonably tight upper bound would be appreciated. I keep on thinking of ways to recursively construct such a circuit but I can't find anything good. Also, any results for any other reasonable basis of allowed gates would also be useful.

$\endgroup$
  • 4
    $\begingroup$ You should remove "..." following the gates and list all the gates you consider acceptable. Otherwise your question cannot be answered, e.g. if we assume that the threshold gate (which is the name of the gate you are asking about) is in the list then the answer is trivial. You should also you should state whether you have unbounded fan-in gates or not. $\endgroup$ – Kaveh Aug 23 '12 at 9:33
8
$\begingroup$

From S. Chaudhuri, J. Radhakrishnan. Deterministic Restrictions in Circuit Complexity:

Theorem 6.1: A circuit computing $T_k^n$ with $k \leq n^{1/3}$ has $\Omega(k^2(\ln n)/\ln k)$ gates

Where $T_k^n$ is the boolean function that has the value 1 iff at least $k$ of its inputs have the value 1 (threshold function).

$\endgroup$
4
$\begingroup$

We can get some sort of upper bound from some complexity inclusions.

$TC^{0}$ is the class of polynomially sized, constant depth boolean circuits where we also have a $MAJORITY$ gate of unbounded fan-in, so there's a size $1$ $TC^{0}$ circuit that computes the function you want (one $MAJ$ gate with all the inputs going to it).

$NC^{1}$ is the class of boolean circuits of polynomial size and $O(\log n)$ depth (but here we only have the normal gates). It is known that $TC^{0} \subseteq NC^{1}$, so at worst, you can compute $MAJ$ with a poly-size $O(\log n)$ depth circuit.

I suspect that as you only need $MAJ$, we can do better, but I haven't managed to get a good reference for this quite yet. Vollmer's "Introduction to Circuit Complexity" should have the reduction, but I don't have a copy available. It should also be a uniform reduction too (i.e. for an input of size $n$ we can efficiently produce the appropriate circuit).

This question on cstheory.SE might also have something useful to you in it, but it's pretty technical.

$\endgroup$
0
$\begingroup$

with $T_k^n$ a standard threshhold function defined as in Vors answer, $T_k^n$ is a symmetric function. thm 2.11.1 in Savage[1] gives a $O(n)$ size circuit.

[1] Models of Computation, John E Savage

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.