patternMinor
Is Space Complexity Always Less Than Or Equal To Time Complexity?
Viewed 0 times
spaceequalthanalwaystimelesscomplexity
Problem
Background
I am working on proving a novel problem to be P-Complete, and this requires using a logspace reduction to reduce some known P-Complete problem to the novel problem. Particularly, I am reducing the Circuit Value Problem, the de facto P-Complete problem, to the novel problem.
The Experienced Difficulty
P-Complete reductions must use logarithmic space in the reduction in order to be meaningful. However, for the novel problem, it is very easy to show that the reduction takes logarithmic time, whereas it is difficult to show that it takes logarithmic space.
The Complicating Factor
There are many Q and A sites online which declare that an algorithm's space complexity is always less than its time complexity. For example: https://www.quora.com/Is-there-any-algorithm-whose-space-complexity-is-more-than-time-complexity. This is just one of many. I have scoured the literature on the subject, reading through Cook, Karp, Stockmeyer, and many more, yet I am unable to find this claim that space complexity is always less than time complexity captured in a rigorous manner. Yet this claim seems pervasive and almost treated as "common knowledge".
Why the Complication Matters
If it is true that space complexity is always less than or equal to time complexity, then instead of doing a logspace reduction, I can show that the reduction can be done in log time, which is much easier in my particular case.
What I Need
Can anyone point me to the paper which established this "common knowledge" idea that space complexity is always less than or equal to time complexity? Or a textbook or other authoritative source?
-Thank You
I am working on proving a novel problem to be P-Complete, and this requires using a logspace reduction to reduce some known P-Complete problem to the novel problem. Particularly, I am reducing the Circuit Value Problem, the de facto P-Complete problem, to the novel problem.
The Experienced Difficulty
P-Complete reductions must use logarithmic space in the reduction in order to be meaningful. However, for the novel problem, it is very easy to show that the reduction takes logarithmic time, whereas it is difficult to show that it takes logarithmic space.
The Complicating Factor
There are many Q and A sites online which declare that an algorithm's space complexity is always less than its time complexity. For example: https://www.quora.com/Is-there-any-algorithm-whose-space-complexity-is-more-than-time-complexity. This is just one of many. I have scoured the literature on the subject, reading through Cook, Karp, Stockmeyer, and many more, yet I am unable to find this claim that space complexity is always less than time complexity captured in a rigorous manner. Yet this claim seems pervasive and almost treated as "common knowledge".
Why the Complication Matters
If it is true that space complexity is always less than or equal to time complexity, then instead of doing a logspace reduction, I can show that the reduction can be done in log time, which is much easier in my particular case.
What I Need
Can anyone point me to the paper which established this "common knowledge" idea that space complexity is always less than or equal to time complexity? Or a textbook or other authoritative source?
-Thank You
Solution
The reason it's common knowledge and not formally proved anywhere is because it's obvious.
During each time step, you can only access one memory location. Therefore you can never access more memory locations than you have time.
I found the following reference, showing an even slightly stronger result: every deterministic multitape Turing machine of time complexity $t(n)$ can be simulated by a deterministic Turing machine of tape complexity $t(n)/\log t(n)$.
If it is true that space complexity is always less than or equal to time complexity, then instead of doing a logspace reduction, I can show that the reduction can be done in log time, which is much easier in my particular case.
This suggests that something is wrong with your understanding. Showing that it runs in logarithmic time is strictly harder than showing it uses logarithmic space. Something really weird has happened. As Robert Anderws rightfully points out in his comment, no reduction from the Circuit Value Problem can run in logarithmic time and be correct, since it can't even read the entire input.
During each time step, you can only access one memory location. Therefore you can never access more memory locations than you have time.
I found the following reference, showing an even slightly stronger result: every deterministic multitape Turing machine of time complexity $t(n)$ can be simulated by a deterministic Turing machine of tape complexity $t(n)/\log t(n)$.
If it is true that space complexity is always less than or equal to time complexity, then instead of doing a logspace reduction, I can show that the reduction can be done in log time, which is much easier in my particular case.
This suggests that something is wrong with your understanding. Showing that it runs in logarithmic time is strictly harder than showing it uses logarithmic space. Something really weird has happened. As Robert Anderws rightfully points out in his comment, no reduction from the Circuit Value Problem can run in logarithmic time and be correct, since it can't even read the entire input.
Context
StackExchange Computer Science Q#115309, answer score: 6
Revisions (0)
No revisions yet.