DTIME (n2)
question: En qué expresión se puede esperar encontrar DTIME (n), context: Para las clases de complejidad definidas de esta manera, es deseable probar que relajar los requisitos en tiempo de computación (por ejemplo) efectivamente define un conjunto más grande de problemas. En particular, aunque DTIME (n) está contenido en DTIME (n2), sería interesante saber si la inclusión es estricta. Para los requisitos de tiempo y espacio, la respuesta a tales preguntas está dada por los teoremas de jerarquía temporal y espacial, respectivamente. Se llaman teoremas de jerarquía porque inducen una jerarquía adecuada en las clases definidas al limitar los recursos respectivos. Por lo tanto, hay pares de clases de complejidad tales que uno está debidamente incluido en el otro. Habiendo deducido tales inclusiones adecuadas, podemos proceder a hacer declaraciones cuantitativas sobre cuánto más tiempo o espacio adicional se necesita para aumentar el número de problemas que se pueden resolver.
En qué expresión se puede esperar encontrar DTIME (n)
En particular, aunque DTIME (n) está contenido en DTIME (n2) ,
Para las clases de complejidad definidas de esta manera, es deseable probar que relajar los requisitos en tiempo de computación (por ejemplo) efectivamente define un conjunto más grande de problemas. En particular, aunque DTIME (n) está contenido en DTIME (n2), sería interesante saber si la inclusión es estricta. Para los requisitos de tiempo y espacio, la respuesta a tales preguntas está dada por los teoremas de jerarquía temporal y espacial, respectivamente. Se llaman teoremas de jerarquía porque inducen una jerarquía adecuada en las clases definidas al limitar los recursos respectivos. Por lo tanto, hay pares de clases de complejidad tales que uno está debidamente incluido en el otro. Habiendo deducido tales inclusiones adecuadas, podemos proceder a hacer declaraciones cuantitativas sobre cuánto más tiempo o espacio adicional se necesita para aumentar el número de problemas que se pueden resolver.
En particular, aunque DTIME (n) está contenido en <hl> DTIME (n2) <hl> ,
Para las clases de complejidad definidas de esta manera, es deseable probar que relajar los requisitos en tiempo de computación (por ejemplo) efectivamente define un conjunto más grande de problemas. En particular, aunque DTIME (n) está contenido en <hl> DTIME (n2) <hl>, sería interesante saber si la inclusión es estricta. Para los requisitos de tiempo y espacio, la respuesta a tales preguntas está dada por los teoremas de jerarquía temporal y espacial, respectivamente. Se llaman teoremas de jerarquía porque inducen una jerarquía adecuada en las clases definidas al limitar los recursos respectivos. Por lo tanto, hay pares de clases de complejidad tales que uno está debidamente incluido en el otro. Habiendo deducido tales inclusiones adecuadas, podemos proceder a hacer declaraciones cuantitativas sobre cuánto más tiempo o espacio adicional se necesita para aumentar el número de problemas que se pueden resolver.
Para las clases de complejidad definidas de esta manera, es deseable probar que relajar los requisitos en tiempo de computación (por ejemplo) efectivamente define un conjunto más grande de problemas. <hl> En particular, aunque DTIME (n) está contenido en DTIME (n2) , <hl> sería interesante saber si la inclusión es estricta. Para los requisitos de tiempo y espacio, la respuesta a tales preguntas está dada por los teoremas de jerarquía temporal y espacial, respectivamente. Se llaman teoremas de jerarquía porque inducen una jerarquía adecuada en las clases definidas al limitar los recursos respectivos. Por lo tanto, hay pares de clases de complejidad tales que uno está debidamente incluido en el otro. Habiendo deducido tales inclusiones adecuadas, podemos proceder a hacer declaraciones cuantitativas sobre cuánto más tiempo o espacio adicional se necesita para aumentar el número de problemas que se pueden resolver.