0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ 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? $\endgroup$
    – Joshua Grochow
    Oct 15, 2013 at 16:37

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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