¿Qué sucede si mejoramos los teoremas de la jerarquía del tiempo?

10

En pocas palabras, los teoremas de la jerarquía del tiempo dicen que una máquina de Turing puede resolver más problemas si tiene más tiempo para el cálculo. En detalle para TM determinístico y funciones construibles en el tiempo con es y para TM no determinista y funciones construibles en el tiempo con es Hay muchos resultados (antiguos y actuales) que utilizan los teoremas de la jerarquía de tiempo para probar los límites inferiores. Aquí están mis preguntas: $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))$

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

$NTIME(f(n)) \subsetneq NTIME(g(n)).$

¿Qué sucede si podemos demostrar un mejor resultado para el caso determinista o no determinista?
Si podemos demostrar que existe una brecha entre la jerarquía de tiempo determinista y la jerarquía de tiempo no determinista, ¿esto implica ? $P \neq NP$

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

Solo una pequeña nota. Para las máquinas de Turing con cinta con , el teorema de la jerarquía de tiempo se puede mejorar: cstheory.stackexchange.com/questions/5297/…

k > 2

$k > 2$

Michael Wehar

4

Sobre tu segunda pregunta. No, eso no implicaría . Los teoremas de jerarquía son principalmente útiles para determinar la cantidad de un solo recurso que necesita una TM para poder resolver problemas adicionales. $P \neq NP$

Por ejemplo, sabemos que . Deje que , , tal que y . $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) )$

De los teoremas de la jerarquía se deduce que y . Bajo esos supuestos, es posible. $DTIME( f(n) ) \subsetneq DTIME( g(n) )$ $NTIME ( f(n) ) \subsetneq NTIME( h(n) )$ $NTIME( g(n) ) \subseteq DTIME( h(n) )$

Los teoremas de la jerarquía se pueden usar para determinar las relaciones entre los recursos, dada una igualdad entre ellos. Por ejemplo, suponga que . Sabemos que , para tal que , no puede ser igual a , debido al teorema de la jerarquía NTIME. $NTIME(2^{n}) = SPACE( n )$ $NTIME( g(n) )$ $g(n)$ $2^{n+1} = o(g(n))$ $SPACE(n)$

chazisop
fuente

1

No veo por qué una brecha no podría implicar . Por supuesto, no es una implicación directa de la brecha, pero tal vez hay otra implicación intermedia que lo implica.

P \neq N P

$P \neq NP$

Marc Bury

0

las jerarquías thms también se refieren a un continuo en el tiempo y el espacio (considerado por separado) y parece posible que el continuo no sea más "granular" de lo que está implícito en los teoremas, es decir, puede ser la mejor "granularidad" posible.

su segunda pregunta parece poco clara o tal vez no está bien definida a menos que pueda definir mejor lo que quiere decir con "brecha". Todos los problemas decidibles se pueden resolver en algún lugar de ambas jerarquías. La dificultad es determinar las interrelaciones. una de las raras "brechas" o separaciones en la teoría actual ha sido probada en tiempo determinista versus tiempo no determinista tal que [1]. ver también [2] para una pregunta similar y avances "recientes" $\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
fuente

¿Qué sucede si mejoramos los teoremas de la jerarquía del tiempo?

Respuestas: