# Lower bounds on counting functions

I have a question about counting problems on arbitrary (not necessarily polynomial time) functions.

Let $F_n = \{f : \{0,1\}^n \to \{0,1\}\}$ be the set of all boolean functions with $n$ inputs (again, not necessarily polynomial time).

Consider the operator $\#: F_n \to \mathbb{N}$ that maps $f \in F_n$ to $\#f = |\{x \in \{0,1\}^n : f(x) = 0\}|$

Consider a computational model where evaluating $f$ on an input $x$ can be done in time O(1). Clearly, the operator #f can be computed in time $O(2^n)$ by a brute force algorithm that evaluates $f$ on all inputs, and counts which of these inputs are zeros of $f$.

My question is, is there an exponential lower bound on the running time of #f?

• Yes. If I understand what you're asking correctly, your question is equivalent to the query complexity of counting the number of zeroes of a black-box boolean function. Telling if there is even one zero requires, in the worst-case, checking all $2^n$ possible inputs to $f$. It's the same as asking: given an input boolean string of length $2^n$, are any of its bits 0? Oct 15 '13 at 16:37

Since you are accessing $f$ in a black box manner, you have to query $f(x)$ at all $2^n$ points. Since otherwise, you can design two functions $f_1$ and $f_2$ that are consistent at all query points yet have different number of zeros.