9
$\begingroup$

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)$?

Improve this question
$\endgroup$
  • $\begingroup$ Note that if $A$ is a sequence with random access, and the sensitivity assumption is weakened, this does not always hold. For example, $(i,x_1,\dots,x_n) \to x_i$ can be computed with two queries, even though it is not a junta. $\endgroup$ – sdcvvc Apr 10 '12 at 22:44
  • $\begingroup$ @sdcvvc your example reminds me the C language instruction V[i]. What is the definition of junta? $\endgroup$ – Виталий Олегович Apr 10 '12 at 22:52
  • 2
    $\begingroup$ A $k$-junta is a boolean function that depends only on $k$ arguments, i.e. there is a set $A\subset\{1,2,\dots,n\}$ of size $k$ such that for any $x$,$y$, if $x$ and $y$ differ only on positions outside $A$, then $f(x)=f(y)$. I abused this term to mean a function that does not depend on all arguments. $\endgroup$ – sdcvvc Apr 10 '12 at 23:18
  • $\begingroup$ If you are trying to find support for your answer to the average distance problem on math.se, unfortunately, this won't do. $\endgroup$ – Aryabhata Apr 11 '12 at 5:38
  • $\begingroup$ @Aryabhata the first intention was to find support for my answer to this question: math.stackexchange.com/questions/129969/…, but the only thing that this result will say is that if there are $n$ vertices in the graph, the algorithm calculating the average distance them will be $\Omega(n)$, which is quite obvius. I have deleted my answer there, because as you wrote I did not prove anything. $\endgroup$ – Виталий Олегович Apr 11 '12 at 7:18
7
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ Sorry I forgot to write that my model of computation was the deterministic Turing machine. $\endgroup$ – Виталий Олегович Apr 10 '12 at 22:07
  • $\begingroup$ +1 for adversary argument, which is a great way to begin understanding lower bounds. $\endgroup$ – Joe Apr 12 '12 at 4:57

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.