I’m a layperson on this topic, but here’s my best understanding of what’s going on.
Take the function unique :: List[Int] -> Bool. There’s an obvious O(n) time algorithm: iterate through the list, throw everything into a hash table, return false if a number appears twice. This also requires (auxiliary) O(n) space, with the worst case being “the only duplicate is in the last element”.
There’s another algorithm you could do: sort the list and then compare adjacent elements. This requires O(nlog(n)) time but only O(1) auxiliary space (for the sort), meaning the “unique problem” has a more spatially efficient solution than it has a temporally efficient solution.
(And here’s where I think I’m already wrong: the two solutions have different auxiliary space usage, but they both have the same overall space complexity O(n), as you need already need that much space to store the whole input! I just don’t know any good examples of total space being more efficient, having thought about this for all of ten minutes).
It’s been known for a long time that this is true in the general case: any problem’s certain time complexity is “larger” than its space complexity. The best bound since 1977 is “not that much more efficiently”: O(f(n)) time can be solved in O(f(n)/log(f(n))) space. So, like O(n²) can be solved in O(n²/log(n)) space, which grows almost as fast as n² anyway.
This paper claims that O(f(n)) time can be solved in O(sqrt(f(n)log(f(n))) space, so O(n²) time can be solved in O(n*sqrt(log(n))) space, which is an enormous improvement. The blog says that if paper passes peer review, it’ll be a major step towards resolving P ≠ PSPACE!
Anyone who’s an actual complexity theorist should please weigh in, I have no idea how much of my understanding is garbage
A lazy space-efficient solution for unique is just O(n^2) compare each element to every other element.
You might be able to get away with the sort if you have some sub-linear auxiliary structure (permutation index?) that lets you un-sort the list when done (if I understand catalytic computing right, which I likely don’t). Edit: never mind, log(n!) to even count the permutations is going to have n outside the log anyway.
Iirc from the lectures I attended a couple months ago, when it comes to log-space or at least less than linear, we treat the input tape as read only, the output tape as write (and maybe also append) only. The Auxiliary space is all you measure, but that readonly-ness is what breaks your sorting solution, because sorting requires mutation or copying. (I’m sure there are other ways of formalising it)
The simple log-space solution would be the brute force compare that @hcs mentioned, I think you would use one pointer/index to each of the two elements you are currently comparing which would take log(n) each.
I mentioned an output tape as the third tape because I was remembering log-space reductions (transforming the input from one problem to another using only log auxiliary space).
The auxiliary space is read+write. So for sublinear space machines you have read only input, sublinear auxiliary space, and the machine either accepts, rejects, or diverges.
In the log space reduction/transducer case I was remembering, you also then output a transformed result into an write only output tape, the key being you can’t store data there (and get around the aux space restriction), only append more output.
Another interesting thing (also pointed out on the wiki linked below) is that you can’t do O(n + log n) read-write input tape, because linear working space can be recovered using the linear speedup theorem (I always think of it as SIMD for Turing machines. You can transform four input binary bits to one hex symbol for example, and make you input 4x smaller at the cost of a bigger state machine).
Some other bits:
Formally, the Turing machine has two tapes, one of which encodes the input and can only be read, whereas the other tape has logarithmic size but can be written as well as read. Logarithmic space is sufficient to hold a constant number of pointers into the input and a logarithmic number of Boolean flags, and many basic logspace algorithms use the memory in this way.
Radix sort is O(n) if the elements of the array have a limited size. More precisely it’s O(nk) where k is the element size, which for integer elements is k = log m where m is the integer value of the largest element.
Edit: and the question of the existence of duplicate elements is only interesting if m > n (otherwise it’s trivially true) so in this context radix sort can’t do better than O(n log n).
I’m a layperson on this topic, but here’s my best understanding of what’s going on.
Take the function
unique :: List[Int] -> Bool. There’s an obvious O(n) time algorithm: iterate through the list, throw everything into a hash table, return false if a number appears twice. This also requires (auxiliary) O(n) space, with the worst case being “the only duplicate is in the last element”.There’s another algorithm you could do: sort the list and then compare adjacent elements. This requires O(nlog(n)) time but only O(1) auxiliary space (for the sort), meaning the “unique problem” has a more spatially efficient solution than it has a temporally efficient solution.
(And here’s where I think I’m already wrong: the two solutions have different auxiliary space usage, but they both have the same overall space complexity O(n), as you need already need that much space to store the whole input! I just don’t know any good examples of total space being more efficient, having thought about this for all of ten minutes).
It’s been known for a long time that this is true in the general case: any problem’s certain time complexity is “larger” than its space complexity. The best bound since 1977 is “not that much more efficiently”: O(f(n)) time can be solved in O(f(n)/log(f(n))) space. So, like O(n²) can be solved in O(n²/log(n)) space, which grows almost as fast as n² anyway.
This paper claims that O(f(n)) time can be solved in O(sqrt(f(n)log(f(n))) space, so O(n²) time can be solved in O(n*sqrt(log(n))) space, which is an enormous improvement. The blog says that if paper passes peer review, it’ll be a major step towards resolving P ≠ PSPACE!
Anyone who’s an actual complexity theorist should please weigh in, I have no idea how much of my understanding is garbage
A lazy space-efficient solution for unique is just O(n^2) compare each element to every other element.
You might be able to get away with the sort if you have some sub-linear auxiliary structure (permutation index?) that lets you un-sort the list when done (if I understand catalytic computing right, which I likely don’t). Edit: never mind, log(n!) to even count the permutations is going to have n outside the log anyway.
Iirc from the lectures I attended a couple months ago, when it comes to log-space or at least less than linear, we treat the input tape as read only, the output tape as write (and maybe also append) only. The Auxiliary space is all you measure, but that readonly-ness is what breaks your sorting solution, because sorting requires mutation or copying. (I’m sure there are other ways of formalising it)
The simple log-space solution would be the brute force compare that @hcs mentioned, I think you would use one pointer/index to each of the two elements you are currently comparing which would take
log(n)each.Ah, that makes so much now. Thank you!
Edit: when you say “write only”, does that mean you can’t write some intermediate result to the aux space and then read it back later?
I mentioned an output tape as the third tape because I was remembering log-space reductions (transforming the input from one problem to another using only log auxiliary space).
The auxiliary space is read+write. So for sublinear space machines you have read only input, sublinear auxiliary space, and the machine either accepts, rejects, or diverges.
In the log space reduction/transducer case I was remembering, you also then output a transformed result into an write only output tape, the key being you can’t store data there (and get around the aux space restriction), only append more output.
Another interesting thing (also pointed out on the wiki linked below) is that you can’t do
O(n + log n)read-write input tape, because linear working space can be recovered using the linear speedup theorem (I always think of it as SIMD for Turing machines. You can transform four input binary bits to one hex symbol for example, and make you input 4x smaller at the cost of a bigger state machine).Some other bits:
https://en.wikipedia.org/wiki/L_(complexity)
And the text book referenced by wikipedia and my lecturer: Sipser 1997 https://fuuu.be/polytech/INFOF408/Introduction-To-The-Theory-Of-Computation-Michael-Sipser.pdf The definition of log space machine is on page 321 (342 of the pdf).
[Comment removed by author]
I think they have the same time complexity as well, since integer sort is O(n) (with any lexicographic sort like radix sort).
Radix sort is O(n) if the elements of the array have a limited size. More precisely it’s O(nk) where k is the element size, which for integer elements is k = log m where m is the integer value of the largest element.
Edit: and the question of the existence of duplicate elements is only interesting if m > n (otherwise it’s trivially true) so in this context radix sort can’t do better than O(n log n).