patternMinor
AND operator of many functions
Viewed 0 times
andfunctionsoperatormany
Problem
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$.
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$.
Solution
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.
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.
Context
StackExchange Computer Science Q#49131, answer score: 5
Revisions (0)
No revisions yet.