Problem Detail: 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 $xin mathbb Z$ such that $f_i(x)=0$ and $f_j(x)=1$ for each $jin {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 $xin 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$.
Asked By : Craig Feinstein
Answered By : Ran G.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/49131 3.2K people like this
