Que se passe-t-il si nous améliorons les théorèmes de la hiérarchie temporelle?

10

En un mot, les théorèmes de la hiérarchie du temps disent qu'une machine de Turing peut résoudre plus de problèmes si elle a plus de temps pour le calcul. En détail pour TM déterministe et fonctions constructibles dans le temps avec c'est et pour TM non déterministe et fonctions constructibles dans le temps f, g avec f (n + 1) = o (g (n)) c'est NTIME (f (n)) \ subsetneq NTIME (g (n)). Il existe de nombreux résultats (anciens et actuels) qui utilisent les théorèmes de la hiérarchie temporelle pour prouver les limites inférieures. Voici mes questions:f,gf(n)log⁡f(n)=o(g(n))

DTIME(f(n))⊊DTIME(g(n))
f,gf(n+1)=o(g(n))
NTIME(f(n))⊊NTIME(g(n)).

  • Que se passe-t-il si nous pouvons prouver un meilleur résultat pour le cas déterministe ou non déterministe?

  • Si nous pouvons prouver qu'il existe un écart entre la hiérarchie temporelle déterministe et la hiérarchie temporelle non déterministe, cela implique-t-il P≠NP ?

cc.complexity-theory lower-bounds big-picture time-complexity time-hierarchy Marc Bury
la source
Juste une petite note. Pour les machines de Turing k-tape avec k>2 , le théorème de la hiérarchie temporelle peut être amélioré: cstheory.stackexchange.com/questions/5297/…
Michael Wehar

Réponses:

4

À propos de votre deuxième question. Non, cela n'impliquerait pas . Les théorèmes de hiérarchie sont principalement utiles pour déterminer la quantité d'une seule ressource nécessaire à une MT afin que des problèmes supplémentaires puissent être résolus.P≠NP

Par exemple, nous savons que . Soit , , tel que et .f ( n ) = n g ( n ) h ( n ) f ( n + 1 ) = o ( g ( n ) ) f ( n ) l o g ( f ( n ) ) = o (DTIME(n)≠NTIME(n)f(n)=ng(n)h(n)f(n+1)=o(g(n))f(n)log(f(n))=o(h(n))

Des théorèmes de hiérarchie, il s'ensuit que et . Dans ces hypothèses, est possible.N T I M E ( f ( n ) ) ⊊ N T I M E ( h ( n ) ) N T I M E ( g ( n ) ) ⊆ D T IDTIME(f(n))⊊DTIME(g(n))NTIME(f(n))⊊NTIME(h(n))NTIME(g(n))⊆DTIME(h(n))

Les théorèmes de hiérarchie peuvent être utilisés pour déterminer les relations entre les ressources, étant donné une égalité entre elles. Par exemple, supposons que . Nous savons que , pour tel que , ne peut pas être égal à , en raison du théorème de la hiérarchie NTIME.N T I M E ( g ( n ) ) g ( n ) 2 n + 1 = o ( g ( n ) ) S P A C E ( n )NTIME(2n)=SPACE(n)NTIME(g(n))g(n)2n+1=o(g(n))SPACE(n)

chazisop
la source
1
Je ne vois pas pourquoi un écart ne pouvait pas impliquer . Bien sûr, ce n'est pas une implication directe de l'écart, mais il y a peut-être une autre implication intermédiaire qui l'implique. P≠NP
Marc Bury
0

la hiérarchie thms concerne également un continuum dans le temps et l'espace (considéré séparément) et il semble possible que le continuum ne soit pas plus "granulaire" que ce que suggèrent les théorèmes, c'est-à-dire qu'ils peuvent être la meilleure "granularité" possible.

votre 2e question semble peu claire ou peut-être pas bien définie à moins que vous ne puissiez mieux définir ce que vous entendez par «écart». tous les problèmes décidables peuvent être résolus quelque part dans les deux hiérarchies. la difficulté est de déterminer les interrelations. l'un des rares «écarts» ou séparations dans la théorie actuelle a en effet été prouvé en temps déterministe vs temps non déterministe tel que [1]. voir aussi [2] pour une question similaire et des avancées "récentes"DTIME(n)≠NTIME(n)

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

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

vzn
la source