patternMinor
Is there a language $L$ such that $L \in DSPACE(1) \setminus DTIME(1)$?
Viewed 0 times
dtimesuchdspacesetminuslanguagethatthere
Problem
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.
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.
Solution
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.
$$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.
Context
StackExchange Computer Science Q#165293, answer score: 2
Revisions (0)
No revisions yet.