Si observamos el teorema de la jerarquía DTIME, tenemos un registro debido a la sobrecarga en la simulación de una máquina de Turing determinista por una máquina universal: DTIME(flogf)⊊DTIME(f)DTIME(flogf)⊊DTIME(f)DTIME(\frac{f}{\log f}) \subsetneq DTIME(f) No tenemos este tipo de gastos...
En una oración: ¿la existencia de una jerarquía para implicaría algún resultado de aleatorización?B P T I M EBPTIME\mathsf{BPTIME} Una pregunta relacionada pero más vaga es: ¿la existencia de una jerarquía para implica algún inferior difícil? ¿La resolución de este problema choca contra una...
El teorema original de la jerarquía del tiempo no determinista se debe a Cook (el enlace es a S. Cook, una jerarquía para la complejidad del tiempo no determinista , JCSS 7 343–353, 1973). El teorema establece que para cualquier número real y , si entonces NTIME ( ) está estrictamente contenido en...
¿Es cierto que hay problemas en la jerarquía polinómica que se pueden resolver en el tiempo (por una máquina de Turing alterna en algún nivel de la jerarquía polinómica) que no se pueden resolver en O ( n k - 1 ) en ningún nivel de jerarquía polinómica? En otras palabras, ¿existe un teorema de...
Defina como la clase de idiomas que puede aceptar una máquina de Turing (multitapa) en el tiempo f ( n ) + 1 . (El " + 1 " es simplemente para simplificar la notación y evitar confusiones). Observe que no hay O ( ⋅ ) alrededor de f ( n ) + 1
El teorema de la jerarquía del tiempo establece que las máquinas de Turing pueden resolver más problemas si tienen (suficiente) más tiempo. ¿Se mantiene de alguna manera si el espacio está limitado asintóticamente? ¿Cómo se relaciona DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n),...
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...
\newcommand{\cc}[1]{\mathsf{#1}} ¿Se un teorema en las siguientes líneas: Si es un poco más grande que , entonces ?f ( n ) N T I M E ( g ) ∩ c o N T I M E ( g ) ≠ N T I M E ( f ) ∩ c o N T I M E ( f )sol( n )g(n)g(n)F( n )f(n)f(n)N T I M E (g) ∩ c o N T I M E ( g) ≠ N T I M E ( f) ∩ c o N T I M E (...