7
$\begingroup$

I am wondering if there are any results to what extent the space and time hierarchies "disagree" on which problem is harder. For example, is it known whether there are languages $L_1$ and $L_2$ such that $L_1 \in \DeclareMathOperator{TIME}{TIME} \TIME(f(n))\setminus SPACE(g(n)),L_2\in \DeclareMathOperator{SPACE}{SPACE} \SPACE(g(n)) \setminus \TIME(f(n))$? How often does this occur?

P.S.- The question Function with space-depending computation time seems to ask something similar but was worded confusingly and none of the answers seem to be what I'm looking for.

$\endgroup$
  • 2
    $\begingroup$ Note that doing this for most standard robust classes (instead of $\mathsf{TIME}(t(n))$ vs $\mathsf{SPACE}(s(n))$) would solve open problems. For example, one natural candidate would be $\mathsf{QP}$ vs. $\mathsf{PSPACE}$. If we could find a function in $\mathsf{QP} \backslash \mathsf{PSPACE}$, that implies $\mathsf{PSPACE} \neq \mathsf{EXP}$, and if we could find a function in $\mathsf{PSPACE} \backslash \mathsf{QP}$ it would imply $\mathsf{P} \neq \mathsf{PSPACE}$. Similarly, finding a function in $\mathsf{P} \backslash \mathsf{L}^2$ would separate $\mathsf{P}$ from $\mathsf{NL}$. $\endgroup$ – Joshua Grochow Feb 18 '18 at 1:49
  • $\begingroup$ Yes, that is a problem. Do you think that this could be remedied by choosing "weirder" complexity classes? They should still be time/space-constructible of course, but perhaps there are more artificial examples of this happening. For example, it seems like choosing $f(n)=n,g(n)=loglogn$ would be hopeful and this wouldn't require solving any huge complexity-theoretic conjectures as far as I know. $\endgroup$ – exfret Feb 18 '18 at 19:47
10
$\begingroup$

You can get the situation you describe by choosing weird functions $f(n)$ and $g(n)$.

For example, let $g(n) = n^3$ and $$f(n) = \begin{cases} n & \text{if $n$ is odd}, \\\ 2^{n^5} & \text{if $n$ is even}. \end{cases} $$

Then choose $L_1$ and $L_2$ as follows:

$L_1$ is a language containing only strings of even length which can be decided in time $O(2^{n^5})$ but not in time $O(2^{n^4})$. The existence of such a language is pretty easy to prove from the time hierarchy theorem.

$L_2$ is a language containing only strings of odd length which can be decided in space $O(n^3)$ but not in space $O(n^2)$. The existence of such a language is pretty easy to prove from the space hierarchy theorem.

Then we have the following facts:

$L_1 \in TIME(f(n))$:

To decide whether a string is in $L_1$, simply check whether the length $n$ is even. If it is, then continue to use the $O(2^{n^5})$ time decider for $L_1$ whose existence is guaranteed by the definition of $L_1$. If $n$ is odd, immediately reject since $L_1$ does not include any odd length strings anyway. This procedure decides $L_1$, runs in time $O(n)$ when $n$ is odd, and runs in time $O(2^{n^5})$ when $n$ is even. In other words, this procedure decides $L_1$ in time $O(f(n))$. As desired, $L_1 \in TIME(f(n))$.

$L_2 \in SPACE(g(n))$:

By the definition of $L_2$, $L_2$ can be decided in space $O(n^3)$. Thus, $L_2 \in SPACE(n^3) = SPACE(g(n))$, as desired.

$L_1 \not\in SPACE(g(n))$:

Suppose for the sake of contradiction that $L_1 \in SPACE(g(n)) = SPACE(n^3)$. We know that $SPACE(n^3) \subseteq TIME(2^{O(n^3)}) \subsetneq TIME(2^{n^4})$. Thus, there exists a decider for $L_1$ which runs in time $O(2^{n^4})$. This directly contradicts the definition of $L_1$. Then by contradiction, we see that $L_1 \not\in SPACE(g(n))$.

$L_2 \not\in TIME(f(n))$:

Suppose for the sake of contradiction that $L_2 \in TIME(f(n))$. This means that there exists a constant $c$ and an algorithm $A$ deciding $L_2$ such that on any input of size $n$, algorithm $A$ terminates in time $c\times f(n)$.

We construct a new algorithm $A'$ as follows: given some input, walk through the entire input, keeping track of whether the input length is even or odd; if at the end of the input the length is determined to be odd, return to the start of the input and run $A$; otherwise, reject. For any input of odd length, $A'$ returns the same answer as $A$. For any input of even length, $A'$ rejects, which matches the expected behavior since $L_2$ contains no even length strings. Thus, $A'$ also decides $L_2$. On even length inputs, $A'$ runs for exactly $n$ steps. On odd length inputs, $A'$ runs for exactly $2n$ steps more than $A$ requires. But $A$ requires at most $c\times f(n)$ steps, which for odd $n$ is $cn$. Thus, in all cases, $A'$ runs in at most $(c+2)n$ steps. In other words, algorithm $A'$ decides $L_2$ in time $O(n)$.

But since $TIME(n) \subseteq SPACE(n)$, we can conclude that $L_2 \in SPACE(n) \subsetneq SPACE(n^2)$. This contradicts the definition of $L_2$. Thus, by contradiction we see that $L_2 \not\in TIME(f(n))$.

$\endgroup$
  • $\begingroup$ Nice! I wonder whether there are examples where both $f,g$ are elementary... $\endgroup$ – Joshua Grochow Feb 19 '18 at 15:10
1
$\begingroup$

In some sense yes, specifically as of right now we have that:

$\textbf{DTIME}(S(n)) \subseteq \textbf{SPACE}(S(n)) \subseteq \textbf{NSPACE}(S(n)) \subseteq \textbf{DTIME}(2^{O(S(n))})$

And also we know that $\textbf{PSPACE} \subsetneq \textbf{EXPSPACE}$ So that also implies $\textbf{P} \subsetneq \textbf{EXPSPACE}$.

Though we don't know what the specific relationships are for example between P and PSPACE, i.e. "is P a proper subset or are they the same?"

As for your question, one thing to note is that the space complexity is always upper bounded by time, since we cannot have that we use $g(n)$ space and $f(n)$ time when $f(n) = \textbf{o}(g(n))$, else it would mean the TM is accessing more cells without needing that many steps.

So for $\textbf{L}_1$ to be in $f(n)$ time and $g(n)$ space would firstly imply that $f(n)$ is somewhat either equals to or larger than $g(n)$. And it'll be the case that it takes more than $g(n)$ space as long as the actual complexity is less than $f(n)$.

Then for $\textbf{L}_2$ since it'll take more than $f(n)$ time, and $g(n)$ space, this is possible as long as we just let the actual time complexity be bigger than $f(n)$ (since the space complexity is already smaller anyway).

Then it'll depend on whether on $\textbf{L}_2$ is in something like $\textbf{EXP}$ whereas $\textbf{L}_1$ is in $\textbf{P}$ for us to conclusively say anything about their relative difficulty, since then we know $\textbf{P} \subsetneq \textbf{EXP}$.

Besides that as far as I know, we can't really tell, since the best we've done so far is the theorem that I firstly mentioned.

I'm sure you can craft up example for things that take greater time and less space as compared to other algorithms. I can't think of any examples of decision problems right now but consider something like dynamic programming, where you can decrease time complexity whilst increasing space complexity.

If you want to know more about that theorem you can try "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak The theorem is mentioned on page 76.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your answer! However, I wasn't looking for results comparing the two hierarchies (I am already familiar with the results you cited). I was looking for languages for which the time hierarchy says $L_2$ is more complex but the space hierarchy says $L_1$ is more complex. $\endgroup$ – exfret Feb 18 '18 at 19:39
  • 1
    $\begingroup$ How about $L_1$ = { <s, t, G> : s is connected to t in directed graph G} and $L_2$ = { <array, d> : there exists a pair of integers in the array such that their sum is d}. $L_1$ can be decided in deterministic linear time and space, whereas $L_2$ can be decided in deterministic quadratic time and logarithmic space. So just set $f(n)$ = O(n) and $g(n)$ to be log(n) and I suppose this example should show there are languages that fit your example? It sure is an interesting question and I don't think I know more about this to give a more well informed answer. $\endgroup$ – CurryKatsuCutlet Feb 19 '18 at 0:43
  • $\begingroup$ Sadly $L_1\in NL$, and it is not known whether $L=NL$. If this were to be true, your example would be incorrect, since then $L_1$ would take logarithmic space. $\endgroup$ – exfret Feb 20 '18 at 14:07
  • $\begingroup$ Hmm yeah that's true. An oversight on my part $\endgroup$ – CurryKatsuCutlet Feb 20 '18 at 15:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.