5
$\begingroup$

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

|cite|improve this question
$\endgroup$
5
+50
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ How do your functions satisfy the property mentioned above in the question? $\endgroup$ – Craig Feinstein Nov 6 '15 at 3:37
  • $\begingroup$ "an algorithm that uses $o(1)$ time" -- typo? $\endgroup$ – Raphael♦ Nov 6 '15 at 8:41
  • $\begingroup$ 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. $\endgroup$ – Craig Feinstein Nov 6 '15 at 14:11
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Craig Feinstein Nov 13 '15 at 4:43
  • 1
    $\begingroup$ 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). $\endgroup$ – D.W.♦ Nov 13 '15 at 5:06
  • $\begingroup$ @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. $\endgroup$ – Craig Feinstein Nov 13 '15 at 13:36
  • $\begingroup$ @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. $\endgroup$ – Craig Feinstein Nov 13 '15 at 17:11

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.