HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is there a language $L$ such that $L \in DSPACE(1) \setminus DTIME(1)$?

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#165293, answer score: 2

Revisions (0)

No revisions yet.