Was passiert, wenn wir die Sätze der Zeithierarchie verbessern?

10

$f,g$ $f(n) \log f(n) = o(g(n))$

D T I M E (f (n)) ⊊ D T I M E (g (n))

$DTIME(f(n)) \subsetneq DTIME(g(n))$

f, g

$f,g$

f (n + 1) = o (g (n))

$f(n+1)=o(g(n))$ es ist

N T I M E (f (n)) ⊊ N T I M E (g (n)) .

$NTIME(f(n)) \subsetneq NTIME(g(n)).$ Es gibt viele (alte und aktuelle) Ergebnisse, die die Zeithierarchiesätze verwenden, um untere Grenzen zu beweisen. Hier sind meine Fragen:

Was passiert, wenn wir ein besseres Ergebnis für den deterministischen oder nichtdeterministischen Fall nachweisen können?
Wenn wir beweisen können, dass es eine Lücke zwischen der deterministischen Zeithierarchie und der nichtdeterministischen Zeithierarchie gibt, impliziert dies $P \neq NP$ ?

cc.complexity-theory lower-bounds big-picture time-complexity time-hierarchy Marc Bury
quelle

Nur eine kleine Notiz. Für K-Tape-Turing-Maschinen mit

k > 2

$k > 2$ kann der Zeithierarchiesatz verbessert werden: cstheory.stackexchange.com/questions/5297/…

Michael Wehar

4

Über deine zweite Frage. Nein, das würde nicht bedeuten $P \neq NP$ . Hierarchiesätze sind meistens nützlich, um die Menge einer einzelnen Ressource zu bestimmen, die von einem TM benötigt wird, damit zusätzliche Probleme gelöst werden können.

Zum Beispiel wissen wir, dass . Sei , , so dass und . $DTIME(n) \neq NTIME(n)$ $f(n) = n$ $g(n)$ $h(n)$ $f(n+1) = o(g(n))$ $f(n)log(f(n)) = o ( h(n) )$

Aus den Hierarchiesätzen folgt und . Unter diesen Annahmen ist möglich. $DTIME( f(n) ) \subsetneq DTIME( g(n) )$ $NTIME ( f(n) ) \subsetneq NTIME( h(n) )$ $NTIME( g(n) ) \subseteq DTIME( h(n) )$

Die Hierarchiesätze können verwendet werden, um Beziehungen zwischen Ressourcen zu bestimmen, wenn eine Gleichheit zwischen ihnen gegeben ist. , . Wir wissen, dass für so dass , aufgrund des NTIME-Hierarchiesatzes nicht gleich kann. $NTIME(2^{n}) = SPACE( n )$ $NTIME( g(n) )$ $g(n)$ $2^{n+1} = o(g(n))$ $SPACE(n)$

Chazisop
quelle

1

Ich verstehe nicht, warum eine Lücke nicht bedeuten kann . Natürlich ist es keine direkte Implikation der Lücke, aber vielleicht gibt es eine andere Zwischenimplikation, die sie impliziert.

P \neq N P

$P \neq NP$

Marc Bury

0

Die Hierarchie handelt auch von einem Kontinuum in Zeit und Raum (getrennt betrachtet), und es scheint möglich, dass das Kontinuum nicht "granularer" ist als in den Theoremen impliziert, dh sie können die bestmögliche "Granularität" sein.

Ihre zweite Frage scheint unklar oder vielleicht nicht genau definiert zu sein, es sei denn, Sie können besser definieren, was Sie unter "Lücke" verstehen. Alle entscheidbaren Probleme sind irgendwo in beiden Hierarchien lösbar. Die Schwierigkeit besteht darin, die Wechselbeziehungen zu bestimmen. Eine der seltenen "Lücken" oder Trennungen in der gegenwärtigen Theorie wurde tatsächlich in der deterministischen Zeit gegenüber der nichtdeterministischen Zeit nachgewiesen, so dass [1]. siehe auch [2] für eine ähnliche Frage und "jüngste" Fortschritte $\mathsf{DTIME}(n) \neq \mathsf{NTIME}(n)$

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

[2] NTIME (n ^ k) ≠ DTIME (n ^ k)?

vzn
quelle

Was passiert, wenn wir die Sätze der Zeithierarchie verbessern?

Antworten: