3
$\begingroup$

It is a very straightforward question.

I know that the following holds, and I know why it holds:

$DTIME(f(n)) \subset DSPACE(f(n))$

However, is there a language $L \in DSPACE(1) \setminus DTIME(1)$? The "1" is supposed to represent a constant complexity.

It seems to me there is not such language but I don't know how to prove it.

$\endgroup$

1 Answer 1

2
$\begingroup$

No. Consider the language

$$L = \{x \in \{0,1\}^* \mid x \text{ has even parity}\},$$

i.e.,

$$L = \{x_1 \cdots x_n \mid x_1 + x_2 + \cdots + x_n \equiv 0 \pmod 2\}.$$

This language is in $\textsf{DSPACE}(1)$ (it can be recognized by a DFA with 2 states, so you only need 1 bit of state), but it is not in $\textsf{DTIME}(O(1))$ (you need to read the entire string to determine its parity, which takes time $\Theta(n)$).

FYI, $\textsf{DSPACE}(O(1))$ is exactly the set of all regular languages. $\textsf{DSPACE}(1)$ is normally taken to be synonymous with $\textsf{DSPACE}(O(1))$. $\textsf{DTIME}(O(1))$ is boring, as it is not possible to read the entire input in $O(1)$ time. It is known that every language in $\textsf{DTIME}(O(n))$ is regular (in fact every language in $\textsf{DTIME}(o(n \log n))$ is regular). See https://math.stackexchange.com/q/84040/14578.

Here is a very nice overview of complexity classes that contains the above result about $DSPACE(O(1))$ and regular languages:

Classifying Problems into Complexity Classes. William Gasarch. November 21, 2015.

$\endgroup$
5
  • $\begingroup$ You assume that the input and working tapes are different. Right? I missed that and suggested a solution (now it is deleted) that shows that the classes are equivalent... but I think the fact that they're different tapes is implicitly assumed as we are talking about sublinear space complexities, which makes sense. $\endgroup$ Jan 29 at 19:24
  • $\begingroup$ @BaderAbuRadi, I have the impression that the standard definition of DSPACE is with respect to deterministic, multi-tape Turing machines (the input tape is read-only, and there is a separate work tape, and the space complexity counts how much space is used on the work tape). See, e.g., en.wikipedia.org/wiki/DSPACE#Machine_models. You might know more than me; do you think I have that wrong? $\endgroup$
    – D.W.
    Jan 29 at 19:30
  • $\begingroup$ You got it right. There is no point in defining sub-linear space complexity using one tape, as reading the input takes at least linear space. We need a separate working tape. Intuitively, it models the "RAM". $\endgroup$ Jan 29 at 19:34
  • $\begingroup$ Regular automata are basically machines without any internal memory, but they can technically work forever, i.e. never halt. Things like $TIME(f(n))\subset SPACE(O(f(n))$ imply that the input has length $n$, whereas regular automata can have arbitrarily long input. So, I would think there actually is a semantic issue here. $\endgroup$
    – rus9384
    Jan 29 at 19:58
  • $\begingroup$ @rus9384, Thank you for taking the time to look at my answer. I don't understand what semantic issue you are thinking of, or how your comments connect to my answer, so I'm not able to respond nor to see how to improve my answer. Sorry. $\endgroup$
    – D.W.
    Jan 29 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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