<p>About your second question. No, that would not imply $P \neq NP$. Hierarchy theorems are mostly useful to determine the amount of a single resource needed by a TM so that additional problems can be solved.</p>

<p>For example, we know that $DTIME(n) \neq NTIME(n)$. Let $f(n) = n$, $g(n)$, $h(n)$ such that $f(n+1) = o(g(n))$ and $f(n)log(f(n)) = o ( h(n) )$. </p>

<p>From the hierarchy theorems it follows that $ DTIME( f(n) ) \subsetneq DTIME( g(n) )$ and $NTIME ( f(n) ) \subsetneq NTIME( h(n) )$.
 Under those assumptions, $ NTIME( g(n) ) \subseteq DTIME( h(n) )$ is possible.</p>

<p>The hierarchy theorems can be used to determine relationships between resources, given an equality between them. For example , assume that
$ NTIME(2^{n}) = SPACE( n )$. We know that $NTIME( g(n) )$, for $g(n)$ such that $2^{n+1} = o(g(n))$, cannot be equal to $SPACE(n)$ , due to the NTIME hierarchy theorem.</p>

CC BY-SA 2.5
2011-03-29T23:37:22.303Z
I don't see why a gap couldn't imply $P \neq NP$. Of course it isn't a direct implication of the gap but perhaps there is a other intermediate implication which implies it.
Marc Bury
CC BY-SA 2.5
2011-03-24T09:17:18.187Z
2011-03-24T09:17:18.187Z
chazisop
<p>the hierarchy thms are also about a continuum in time and space (considered separately) and it seems possible the continuum is not more "granular" than is implied in the theorems, ie they may be the best possible "granularity".</p>

<p>your 2nd question seems unclear or maybe not well defined unless you can better define what you mean by "gap". all decidable problems are solvable somewhere in both hierarchies. the difficulty is to determine the interrelationships. one of the rare "gaps" or separations in current theory has indeed been proven in deterministic time vs nondeterministic time such that $\mathsf{DTIME}(n) \neq \mathsf{NTIME}(n)$ [1]. see also [2] for a similar question &amp; "recent" advances</p>

<p>[1] PPST1983 <a href="http://dl.acm.org/citation.cfm?id=1382850" rel="nofollow noreferrer">http://dl.acm.org/citation.cfm?id=1382850</a></p>

<p>[2] <a href="https://cstheory.stackexchange.com/questions/1079/ntimenk-dtimenk/9676#9676">NTIME(n^k) ≠ DTIME(n^k) ?</a></p>

CC BY-SA 3.0
2012-01-09T23:43:17.263Z
2012-01-09T23:43:17.263Z
2017-04-13T12:32:28.743Z
vzn
<p>In a nutshell, the <a href="http://en.wikipedia.org/wiki/Time_hierarchy_theorem">time hierarchy theorems</a> say that a Turing machine can solve more problems if it has more time for computation. In detail for deterministic TM and time-constructable functions $f,g$ with $f(n) \log f(n) = o(g(n))$ it is
$$ DTIME(f(n)) \subsetneq DTIME(g(n))$$
and for nondeterministic TM and time-constructable functions $f,g$ with $f(n+1)=o(g(n))$ it is
$$ NTIME(f(n)) \subsetneq NTIME(g(n)).$$
There are a lot of (old and current) results which use the time hierarchy theorems to prove lower bounds. Here are my questions:</p>

<ul>
<li><p>What happens if we can prove a better
result for the deterministic or nondeterministic case?</p></li>
<li><p>If we can prove that there is a gap
between the deterministic time
hierarchy and the nondeterministic
time hierarchy, does this imply $P \neq
   NP$?</p></li>
</ul>

CC BY-SA 3.0
2016-04-29T07:49:31.500Z
Just a small note.  For k-tape Turing machines with $k > 2$, the time hierarchy theorem can be improved: http://cstheory.stackexchange.com/questions/5297/justification-of-log-f-in-dtime-hierarchy-theorem
Michael Wehar
<cc.complexity-theory><lower-bounds><big-picture><time-complexity><time-hierarchy>
What happens if we improve the time hierarchy theorems?
Marc Bury
# What happens if we improve the time hierarchy theorems?

(Asked by: username_0 on 2011-03-24)

In a nutshell, the [time hierarchy theorems](http://en.wikipedia.org/wiki/Time_hierarchy_theorem) say that a Turing machine can solve more problems if it has more time for computation. In detail for deterministic TM and time-constructable functions $f,g$ with $f(n) \log f(n) = o(g(n))$ it is
$$ DTIME(f(n)) \subsetneq DTIME(g(n))$$
and for nondeterministic TM and time-constructable functions $f,g$ with $f(n+1)=o(g(n))$ it is
$$ NTIME(f(n)) \subsetneq NTIME(g(n)).$$
There are a lot of (old and current) results which use the time hierarchy theorems to prove lower bounds. Here are my questions:

* What happens if we can prove a better
  result for the deterministic or nondeterministic case?
* If we can prove that there is a gap
  between the deterministic time
  hierarchy and the nondeterministic
  time hierarchy, does this imply $P \neq
  NP$?

**Tags:** cc.complexity-theory, lower-bounds, big-picture, time-complexity, time-hierarchy
> **Comments:**
> **username_1**: Just a small note.  For k-tape Turing machines with $k > 2$, the time hierarchy theorem can be improved: http://cstheory.stackexchange.com/questions/5297/justification-of-log-f-in-dtime-hierarchy-theorem  

---

## 2 answers

### Answer by username_2 on 2011-03-24. Score: 4

About your second question. No, that would not imply $P \neq NP$. Hierarchy theorems are mostly useful to determine the amount of a single resource needed by a TM so that additional problems can be solved.

For example, we know that $DTIME(n) \neq NTIME(n)$. Let $f(n) = n$, $g(n)$, $h(n)$ such that $f(n+1) = o(g(n))$ and $f(n)log(f(n)) = o ( h(n) )$.

From the hierarchy theorems it follows that $ DTIME( f(n) ) \subsetneq DTIME( g(n) )$ and $NTIME ( f(n) ) \subsetneq NTIME( h(n) )$.
Under those assumptions, $ NTIME( g(n) ) \subseteq DTIME( h(n) )$ is possible.

The hierarchy theorems can be used to determine relationships between resources, given an equality between them. For example , assume that
$ NTIME(2^{n}) = SPACE( n )$. We know that $NTIME( g(n) )$, for $g(n)$ such that $2^{n+1} = o(g(n))$, cannot be equal to $SPACE(n)$ , due to the NTIME hierarchy theorem.

> **Comments:**
> **username_0**: I don't see why a gap couldn't imply $P \neq NP$. Of course it isn't a direct implication of the gap but perhaps there is a other intermediate implication which implies it.  

---

### Answer by username_3 on 2012-01-09. Score: 0

the hierarchy thms are also about a continuum in time and space (considered separately) and it seems possible the continuum is not more "granular" than is implied in the theorems, ie they may be the best possible "granularity".

your 2nd question seems unclear or maybe not well defined unless you can better define what you mean by "gap". all decidable problems are solvable somewhere in both hierarchies. the difficulty is to determine the interrelationships. one of the rare "gaps" or separations in current theory has indeed been proven in deterministic time vs nondeterministic time such that $\mathsf{DTIME}(n) \neq \mathsf{NTIME}(n)$ [1]. see also [2] for a similar question & "recent" advances

[1] PPST1983 <http://dl.acm.org/citation.cfm?id=1382850>

[2] [NTIME(n^k) ≠ DTIME(n^k) ?](https://cstheory.stackexchange.com/questions/1079/ntimenk-dtimenk/9676#9676)


---

