[Solved]: Lower bounds of calculating a function of a set

Problem Detail: 

Having a set $A$ of $n$ elements, let's say I want to calculate a function $f(A)$ that is sensitive to all parts of the input, i.e. depends on very member of $A$ (i.e. it is possible to change any member of $A$ to something else to obtain a new input $A'$ s.t. value of $f$ on $A$ and $A'$ are different).

For example, $f$ could be the sum or the average.

Is there a result that proves that, under some conditions, the time necessary to a deterministic Turing machine to compute $f$ will be $\Omega(n)$?

Asked By : Vitalij Zadneprovskij

Answered By : Kaveh

You have to be specify the model of computation and properties of $f$. In the following argument I will state the assumptions that I need. It can be generalized a little bit further but I think it should be sufficient to give you the idea.

Assume that the machine $M$ never reads the value of one of the members of $A$ (a fixed set, and $A$ is given as a list). Assume further that $A$ is an input such that changing the value of its $i$th member does not change $M$'s answer. Assume further that $f$ is sensitive to all parts of the input, i.e. depends on very member of $A$ (i.e. it is possible to change any member of $A$ to something else to obtain a new input $A'$ s.t. value of $f$ on $A$ and $A'$ are different).

We can use an adversary argument to show that the machine cannot compute the right answer by changing the value of that member of $A$ to obtain $A'$ else s.t. the value of $f$ is different. The value of $M$ on these two sets is the same, so one of them must be false and therefore $M$ cannot compute $f$ correctly.

Therefore any machine $M$ that computes $f$ will need to read all of the input which takes $\Omega(n)$ steps.

(On the other hand, assume that we have a nondeterministic random access machine, and we want to compute OR of the bits in the input. We can nondeterministicly guess a bit and check if that is 1, if it is 1, we output 1. This machine reads only a single bit of the input in $O(\lg n)$ steps and correctly answers the problem. So without assumptions on $M$ and $f$ the result does not hold.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1218

 Ask a Question

 Download Related Notes/Documents