8
$\begingroup$

Is it known whether SPACE(n) (the class of languages recognized by deterministic TMs with linear space) is a proper subset of E (the class of languages recognized by deterministic TMs in time 2^O(n))?

$\endgroup$
  • 3
    $\begingroup$ of course the key word here is 'proper' since containment is trivial. $\endgroup$ – Suresh Venkat Sep 23 '10 at 21:40
16
$\begingroup$

If in fact DSPACE(n) = E, then a padding argument would translate this to PSPACE=EXP. Similarly, if DSPACE(n) $\neq$ E then a padding argument would translate this to L $\neq$ P.

$\endgroup$
  • $\begingroup$ I don't see why DSPACE(n) ≠ E translates to L ≠ P. Padding argument is a tool to conditionally prove that if some complexity classes are equal, then some other bigger classes are also equal. (See: en.wikipedia.org/wiki/Padding_argument) $\endgroup$ – M.S. Dousti Sep 23 '10 at 23:36
  • 4
    $\begingroup$ +1 for succinctness! @Sadeq: That's right. Take the contrapositive of your claim. You'll get "If bigger classes are not equal then smaller classes are not equal." $\endgroup$ – Robin Kothari Sep 24 '10 at 0:02
  • $\begingroup$ @Robin: You're right. I didn't see the obvious :) $\endgroup$ – M.S. Dousti Sep 24 '10 at 0:09
1
$\begingroup$

Note Before Reading

The following proof is flawed, as pointed out in a comment below by Robin Kothari. I'm thankful to him for clarifying the point. However, I didn't remove this answer since I think it is instructive to be aware of such flaw.


I think the "proper" part can be proved using time and space hierarchy theorems. (See sections 7.2 & 7.3 of the Papadimitriou's Computational Complexity).

For a time- and space-constructible function $f(n) \ge n$ we have:

$DSPACE(f(n)) \subseteq NSPACE(f(n))$

$\exists k \quad NSPACE(f(n)) \subseteq DTIME(k^{\log n + f(n)})$

$DTIME(f(n)) \subset DTIME(f(n)\log^2 f(n))$

($\subset$ denotes proper subset.)

Hence, for the linear function $f(n)=n$, there exists a $k$ such that:

$DSPACE(n) \subseteq DTIME(k^{\log n + n}) \subseteq DTIME(k^{2n}) \subset DTIME((k^{2n})(\log^2 (k^{2n})))$

The right-hand side is a proper subset of E.

$\endgroup$
  • $\begingroup$ This is wrong. In the above k depends on the particular language. $\endgroup$ – Kristoffer Arnsfelt Hansen Sep 23 '10 at 23:20
  • $\begingroup$ Could you elaborate on what language are you speaking about? And in any case, isn't it enough to assume that some k exists? $\endgroup$ – M.S. Dousti Sep 23 '10 at 23:39
  • $\begingroup$ Such a k exists for each language in DSPACE(n). That is, if you give me a language L in DSPACE(n), I'll give you a k for which L is also in $DTIME(k^{2n})$. But this doesn't tell us that there is one k that just works for all languages in DSPACE(n). $\endgroup$ – Robin Kothari Sep 24 '10 at 0:20
  • $\begingroup$ @Robin: Thanks Robin. I understood the flaw, and edited the answer to warn the reader that it is flawed. $\endgroup$ – M.S. Dousti Sep 24 '10 at 5:35
0
$\begingroup$

The complexity zoo reports that E does not equal PSPACE, citing the paper Comparing complexity classes by Ronald V. Book.

The following sentences can be easily derived:

SPACE(n) is a proper subset of PSPACE. (1)
PSPACE union E is non-empty. (2)

IF instead of E we had EXPTIME, it would be easy to deduce that SPACE(n) is a proper subset of EXPTIME, due to (1) and that PSPACE is a subset of EXPTIME.

For E, the relationship between PSPACE and E is unclear to me :

1) Is E contained in PSPACE?

If not, then it follows that SPACE(n) is a proper subset of E. To verify this, one must create a problem that uses more than linear space and less than O(2n) time.

2) Is PSPACE contained in E?

This I believe, is even harder to answer than the previous question.

$\endgroup$
  • 1
    $\begingroup$ Can you explain the argument behind "Since SPACE(n) is a subset of PSPACE, it follows that SPACE(n) does not equal E"? $\endgroup$ – Robin Kothari Sep 26 '10 at 16:37
  • $\begingroup$ The argument is valid for EXPTIME, I don't know if it is valid for E. See the edited answer for more details. $\endgroup$ – chazisop Sep 27 '10 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy