<p>The $\mathsf{P} \neq \mathsf{PSpace}$ conjecture means that</p>

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

<p>But I need a stronger assumption</p>

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

<p>Obviously the <a href="https://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="nofollow">Exponential Time Hypothesis (ETH)</a> implies the statement above: 
3SAT is in linear space.
But I don't want to assume ETH.</p>

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

CC BY-SA 3.0
2014-05-14T19:01:46.157Z
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
CC BY-SA 3.0
2014-05-14T19:10:57.333Z
@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
CC BY-SA 3.0
2014-05-14T19:20:50.080Z
But @JeremyKun, is there a reason you care about linear space rather than polynomial space?
usul
CC BY-SA 3.0
2014-05-14T19:27:08.307Z
@SureshVenkat Even easier, TQBF is in SPACE(n).
Jeremy Kun
CC BY-SA 3.0
2014-05-14T19:29:08.923Z
@usul I do care about linear space in particular, because I'm trying to use this language I get to prove something about a different linear-space-bounded class.
Jeremy Kun
CC BY-SA 3.0
2014-05-15T17:28:58.357Z
@RickyDemer good point.
Jeremy Kun
CC BY-SA 3.0
2014-05-15T18:55:28.047Z
If people conjecture ETH then obviously they also conjecture that TQBF requires exponential time. If you are among if that is a plausible conjecture them the answer is yes. If you are asking if that has a name then I think the answer is no. It seems to me what you want to know is if it is plausible to conjecture that TQBF requires exponential time but SAT doesn't.
Kaveh
CC BY-SA 3.0
2014-05-15T19:44:42.547Z
@Kaveh Moreover, do we know anything about how much weaker the conjecture that TQBF requires exponential time is than ETH? Or if you don't want to talk about TQBF, might there be an even weaker assumption that *some* linear space language requires exponential time, even if neither TQBF nor SAT do?
Jeremy Kun
CC BY-SA 3.0
2014-05-15T23:01:15.153Z
@Ricky, OK, you are right. Now I am not sure if Jeremy really needs $2^{\Omega(n)}$ or if $2^{\Omega(n / \lg n)}$ is enough.
Kaveh
<cc.complexity-theory><complexity-classes><time-complexity><space-complexity><pspace>
Linear space language that requires exponential time without ETH
Jeremy Kun
# Linear space language that requires exponential time without ETH

(Asked by: username_0 on 2014-05-14)

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)](https://en.wikipedia.org/wiki/Exponential_time_hypothesis) 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?

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, space-complexity, pspace

> **Comments:**
> **username_1**: Why does $P \ne PSPACE$ give you (1) ? it could be that the language(s) separating P from PSPACE require $n^{10}$ space ?  
> **username_2**: @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$).  
> **username_2**: But @JeremyKun, is there a reason you care about linear space rather than polynomial space?  
> **username_0**: @SureshVenkat Even easier, TQBF is in SPACE(n).  
> **username_0**: @username_2 I do care about linear space in particular, because I'm trying to use this language I get to prove something about a different linear-space-bounded class.  
> **username_0**: @RickyDemer good point.  
> **username_3**: If people conjecture ETH then obviously they also conjecture that TQBF requires exponential time. If you are among if that is a plausible conjecture them the answer is yes. If you are asking if that has a name then I think the answer is no. It seems to me what you want to know is if it is plausible to conjecture that TQBF requires exponential time but SAT doesn't.  
> **username_0**: @username_3 Moreover, do we know anything about how much weaker the conjecture that TQBF requires exponential time is than ETH? Or if you don't want to talk about TQBF, might there be an even weaker assumption that *some* linear space language requires exponential time, even if neither TQBF nor SAT do?  
> **username_3**: @Ricky, OK, you are right. Now I am not sure if Jeremy really needs $2^{\Omega(n)}$ or if $2^{\Omega(n / \lg n)}$ is enough.  

---

## 0 answers

