10
$\begingroup$

In a nutshell, the time hierarchy theorems 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$?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Marc Bury
    Mar 29, 2011 at 23:37
0
$\begingroup$

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) ?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.