World's most popular travel blog for travel bloggers.

[Solved]: How to prove strict space lower bounds using crossing sequences in Turing machines?

, , No Comments
Problem Detail: 

I understand the notion of crossing sequences when talking about time, however how are they used to actually prove strict lower bounds for some decision/search problems?

For example, suppose that you have an array of size N and you want to find the maximum number in it.

Speaking informally, we need at least a pointer to run through the input and some other variable to update whenever we find a number in the input tape that is bigger than the temporary number in our work tape, thus leading us to use Ω(logn) space.

However, how can you prove that you can't do it in O(1) space? Many articles online are using crossing sequences for proving space lower bounds, but they don't show how to do it, they just say something along the lines of "using crossing sequences it's trivial to show that the space lower bound is ..."

which isn't very helpful for beginners like me. Thanks!

Asked By : jsguy

Answered By : Yuval Filmus

A deterministic algorithm running in space $S$ runs in time $\exp S$. If you don't go over the entire array then you don't know the maximum number (formally speaking, consider two arrays differing in the last element, in only one of which it is the maximum). It takes time $n$ to go over the entire array. So $S = \Omega(\log n)$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback