2
$\begingroup$

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

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ What is your model of computation? If your reduction runs in logarithmic time on a Turing machine, it cannot read all of the input to the original problem. $\endgroup$ – Robert Andrews Oct 1 '19 at 13:07
  • $\begingroup$ @RobertAndrews , I have provided more details in the comments to the answer posted by Tom van der Zanden. $\endgroup$ – Serenity Rising Oct 1 '19 at 20:27
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ that is a very intuitive explanation for why the space complexity is always les than or equal to the time complexity. Thank you! The "something weird" that is happening may be due to the fact that I am in fact using an NC reduction to show that the novel problem is P-Complete. According to: link, "The class of P-complete problems is closed under the relation of NC-reduction: If L2 in P and there exists P-complete L1 such that L1<=nc L2, then L2 is P-complete." I am using an NC reduction because the novel problem.. $\endgroup$ – Serenity Rising Oct 1 '19 at 20:16
  • $\begingroup$ … involves a Markov Decision Process with a tree structure, which makes parallelization easy. Additionally, there is a single calculation involved in the reduction, that being (0.5)^(2N-1), which lends itself to parallelization since the repeated power can be implemented as a multiplication tree with multiple processors. With the NC reduction, I can reduce the novel problem to the Circuit Value Problem in logarithmic time on a polynomial number of processors. My reasoning is that if the reduction is done in log time in this way, then the space must also be bounded. But perhaps the (0.5)^(2N-1) $\endgroup$ – Serenity Rising Oct 1 '19 at 20:24
  • $\begingroup$ calculation makes this untrue? If the processors used in the NC reduction share their memory, then the NC reduction might be able to be done in log time on a polynomial number of processors, but use more than log space? $\endgroup$ – Serenity Rising Oct 1 '19 at 20:26
  • $\begingroup$ This helps to clear things up. Tom, myself, and any reference saying "space is bounded by time" are all speaking about sequential computation. It is known that $\mathsf{NC^1} \subseteq \mathsf{L}$, which follows from bounding the space used by a sequential algorithm simulating the corresponding parallel algorithm. Here $\mathsf{NC^1}$ refers to the class of problems solvable in $O(\log n)$ time with $n^{O(1)}$ processors. $\endgroup$ – Robert Andrews Oct 2 '19 at 12:32
  • $\begingroup$ I should also add that in the context of your original question, this is not so much of an issue. When defining $\mathsf{P}$-completeness, we have to use some notion of reduction which is stronger than polynomial-time reducibility. If we don't do this, almost all problems in $\mathsf{P}$ are $\mathsf{P}$-complete for trivial reasons. The common response to this is to use logspace reducibility. However, using an $\mathsf{NC}$ reduction is fine, as this doesn't lead to an immediately trivial definition of $\mathsf{P}$-completeness. $\endgroup$ – Robert Andrews Oct 2 '19 at 12:37

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.