# Linear space language that requires exponential time without ETH

The $\mathsf{P} \neq \mathsf{PSpace}$ conjecture means that

There is a language $L \in \mathsf{DSpace}(O(n^t))$ for some $t>0$ such that for all positive integers $k$, $L$ requires $\Omega(n^k)$ deterministic time to decide.

But I need a stronger assumption

There is a language in $\mathsf{DSpace}(O(n))$ that requires exponential ($2^{\Omega(n)}$) deterministic time to decide.

Obviously the Exponential Time Hypothesis (ETH) implies the statement above: 3SAT is in linear space. But I don't want to assume ETH.

Is there a weaker conjecture (something that is plausible even if ETH is false) that I can use?

• Why does $P \ne PSPACE$ give you (1) ? it could be that the language(s) separating P from PSPACE require $n^{10}$ space ? – Suresh Venkat May 14 '14 at 19:01
• @SureshVenkat, I guess a padded version of that language works (append $n^{10}$ zeroes to every string, the new language needs only linear space but is still not in $P$). – usul May 14 '14 at 19:10
• @SureshVenkat Even easier, TQBF is in SPACE(n). – Jeremy Kun May 14 '14 at 19:27
• ${}$#2 $\; \implies \;$ $L \not\in \operatorname{TIME}(n^k) \;\;$, $\;\;$ so you can simplify #1. $\;\;\;\;\;$ – user6973 May 15 '14 at 17:15
• @Kaveh : $\;\;\;$ I think you confused size-of-an-instance with number-of-variables-in-an-instance. $\:$ If no, now can one show that ETH implies the existence of a language as described above? $\;\;\;\;\;\;\;$ – user6973 May 15 '14 at 21:53