A known theorem staes that if $f$ is a function from $\left\{0,1\right\}^{n}$ to $\{0,1\right\}$ that has a critical input, cannot be computed by any CREW PRAM machine (i.e. regardless of the number of processors) in less than $\log_{2}\left(n\right)$.
A function as above has a critical input if there exist $I\in\left\{0,1\right\}^{n}$ such that $f\left(I\right)\not = f\left(I_{j}\right)$ for any $j$, where $I_{j}$ is $I$ cahged in a single bit in the $j$'th place.
I will be happy if one can advise some refference regarding a simple proof of this theorem.
- Badges
- Science topic
- Similar topics
- Psychology
- Emotional Psychology
- Happiness
More Yossi Peretz's questions See All
Similar questions and discussions