# AND operator of many functions

Suppose we have a set of functions $f_i: \mathbb Z \rightarrow \{0,1\}, i=1, \dots,n$, with the following property:

For each $i =1,\dots ,n$, there exists an $x\in \mathbb Z$ such that $f_i(x)=0$ and $f_j(x)=1$ for each $j\in \{1,\dots,i-1,i+1,\dots,n\}$. Also, there exists an $x \in \mathbb Z$ such that $f_i(x)=1$ for each $i$.

Let $x\in \mathbb Z$. In order to determine whether $f_1(x)$ AND $f_2(x)$ AND ... AND $f_n(x)$, is it necessary to compute each $f_i(x)$ until one of these functions is found to be zero or until all functions are found to be one, which would take $\Omega(n)$ time in the worst case scenario?

Added to clarify: The functions $f_i$ are known. The input is $x \in \mathbb Z$.

When $f_i$ are given as black boxes, it takes $\Omega(n)$ in the worst case to compute their AND.

The constraints that the question puts on the functions $f_i$, don't really tell anything about $f_i$ and their behavior, maybe except for a very small subset of inputs. For instance, we can assume that over the inputs $x=0,...,n$ each $f_i$ is 1, except for the case where $x=i$. This satisfies all the constraints stated. But if $x>n$ we have no idea how $f_i$ behaves. As a trivial example, it can be that each $f_i$ has some infinite kernel (=values of $x$ that zeroize it), but the union of all the kernels doesn't cover the entire $\mathbb{Z}$. As a block box, it is not clear that you even have a compact way to describe each kernel, and you have no choice but querying the black box.

Even if the kernel of each function is known (and has a compact description), it can be that the most compact description of their union is "the union of the kernel of $f_1$ and $f_2$ and ...", which hints that one must compute each $f_i$ separately to know their AND value. For instance, if $f_1$ is the indicator function of all the prime numbers, and $f_2$ is the indicator of all odd numbers whose binary representation has an equal number of ones and zeros. Probably simpler examples can be found.

If we only have black-box access to the functions $f_i$ (they are provided as oracles), then yes, it takes $\Omega(n)$ time. For instance, suppose $f_i(1000+i)=0$ and $f_i(1000+j)=1$ for $j\ne i$. This does not constrain the behavior of $f_i$ for $x<1000$, so does not provide any useful information about the $f_i$'s. Then it is possible to prove a $\Omega(n)$ time bound for queries about $x$ (when $x<1000$) using an adversary argument.

However, don't mis-interpret this! Don't assume this means that $\Omega(n)$ time is needed when the algorithm has access to a description of the $f_i$'s. An algorithm that is provided circuits or code for the $f_i$'s might well be able to do better.

For instance, suppose all the $f_i$'s come from the class if affine functions ($f_i(x)=\alpha_i x + \beta_i$), and we are given a mathematical expression for each $f_i$ (we are given the $\alpha_i$'s and $\beta_i$'s). Then there is an algorithm that uses $o(1)$ time, in this scenario. In particular, we know that $f_i(x)=0$ if and only if $x_i = -\beta_i/\alpha_i$. Therefore, we can precompute the value of all $-\beta_i/\alpha_i$; either they are all equal to some value, say $c$, or they are not all equal. If they are not all equal, then the answer to any query about any particular $x$ is always "False". If they are all equal to $c$, then the answer to a query about a particular $x$ is always "True if $x=c$, False otherwise". In both cases, you can answer queries about a particular $x$ in $O(1)$ time.

So, the $\Omega(n)$ time bound I mentioned in the first paragraph probably will not apply to most real-world situations that arise in practice.

• How do your functions satisfy the property mentioned above in the question? – Craig Feinstein Nov 6 '15 at 3:37
• "an algorithm that uses $o(1)$ time" -- typo? – Raphael Nov 6 '15 at 8:41
• I don't see how this algorithm would take $O(1)$ time in the worst-case scenario. You still need to check each $-\beta_i/\alpha_i$ to see if it matches $x_i$, which would take $\Omega(n)$ time. – Craig Feinstein Nov 6 '15 at 14:11

Suppose we define $f_i$ so that $f_i(x)=1$ for each $i=1,\dots,n$ whenever $x$ is even and $f_i(x)=0$ for some $i \in \{1,\dots,n\}$ whenever $x$ is odd so that the functions satisfy the constraints given in the question. Then we can compute $f_1(x)$ AND $f_2(x)$ AND ... AND $f_n(x)$ by just checking whether $x$ is even or odd. [For instance, if $n=3$, we could define $f_1(1)=0, f_2(1)=f_3(1)=1$, $f_1(3)=f_3(3)=1, f_2(3)=0$, $f_2(5)=f_3(5)=1, f_1(5)=0$ and $f_i(x)=1$ whenever $x$ is even and it will satisfy the constraints. It is possible do this for general $n$.]

So the answer to the question is that it is not necessarily true that one must compute each function $f_i(x)$ until one is found to be zero or until all are found to be one.

• @D.W. If we define $f_i$ properly when $x$ is odd, it will satisfy the constraints outlined in the question. For instance, if $n=3$, we could define $f_1(1)=0, f_2(1)=f_3(1)=1$, $f_1(3)=f_3(3)=1, f_2(3)=0$, $f_2(5)=f_3(5)=1, f_1(5)=0$ and $f_i(x)=1$ whenever $x$ is even and it will satisfy the constraints. I didn't exactly specify how to do this for general $n$ but it is pretty easy to see that it is possible. – Craig Feinstein Nov 13 '15 at 4:43
• A more significant concern I have is that the question seems to be asking about worst-case running time, but you can't draw inferences about the worst-case running time by looking at one example of the best case (by exhibiting one problem instance where the problem can be solved efficiently). – D.W. Nov 13 '15 at 5:06
• @D.W. Remember that the functions $f_i$ are known before the problem is given, so if we were to generalize the example I gave for any $n$, we would find that the algorithm would still run in constant time, as one would only need to check whether $x$ is even or odd. – Craig Feinstein Nov 13 '15 at 13:36
• @D.W., I am guessing that one could find non-black-box functions such that the worst case running-time is $\Omega(n)$. My answer is just that this doesn't always happen. – Craig Feinstein Nov 13 '15 at 17:11