8
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Why does $P \ne PSPACE$ give you (1) ? it could be that the language(s) separating P from PSPACE require $n^{10}$ space ? $\endgroup$ – Suresh Venkat May 14 '14 at 19:01
  • 1
    $\begingroup$ @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$). $\endgroup$ – usul May 14 '14 at 19:10
  • 2
    $\begingroup$ @SureshVenkat Even easier, TQBF is in SPACE(n). $\endgroup$ – Jeremy Kun May 14 '14 at 19:27
  • 1
    $\begingroup$ ${}$#2 $\; \implies \;$ $L \not\in \operatorname{TIME}(n^k) \;\;$, $\;\;$ so you can simplify #1. $\;\;\;\;\;$ $\endgroup$ – user6973 May 15 '14 at 17:15
  • 1
    $\begingroup$ @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? $\;\;\;\;\;\;\;$ $\endgroup$ – user6973 May 15 '14 at 21:53

Your Answer

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

Browse other questions tagged or ask your own question.