<p>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.</p>

CC BY-SA 3.0
2013-10-15T16:40:10.643Z
2013-10-15T16:40:10.643Z
Mahdi Cheraghchi
<p>I have a question about counting problems on arbitrary (not necessarily polynomial time) functions.</p>

<p>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).</p>

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

<p>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$.</p>

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

CC BY-SA 3.0
2013-10-15T16:37:55.883Z
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?
Joshua Grochow
<lower-bounds><counting-complexity>
Lower bounds on counting functions
Asterix
# Lower bounds on counting functions

(Asked by: username_0 on 2013-10-15)

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?

**Tags:** lower-bounds, counting-complexity

> **Comments:**
> **username_1**: 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?  

---

## 1 answers

### Answer by username_2 on 2013-10-15. Score: 1 | Accepted answer

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.


---

