DTIME (f (n))
question: ¿Cuál es la expresión utilizada para identificar una serie dada de problemas capaces de ser resueltos en el tiempo en una máquina de Turing determinista?, context: Para una definición precisa de lo que significa resolver un problema usando una determinada cantidad de tiempo y espacio, se utiliza un modelo computacional como la máquina de Turing determinista. El tiempo requerido por una máquina de Turing determinista M en la entrada x es el número total de transiciones de estado, o pasos, la máquina hace antes de que se detiene y da la respuesta ("sí" o "no"). Se dice que una máquina de Turing M opera dentro del tiempo f (n), si el tiempo requerido por M en cada entrada de longitud n es a lo sumo f (n). Un problema de decisión A puede ser resuelto en tiempo f (n) si existe una máquina de Turing operando en tiempo f (n) que resuelve el problema. Dado que la teoría de la complejidad está interesada en clasificar problemas basados en su dificultad, se definen conjuntos de problemas basados en algunos criterios. Por ejemplo, el conjunto de problemas solucionables dentro del tiempo f (n) en una máquina de Turing determinista se denota entonces por DTIME (f (n)).
¿Cuál es la expresión utilizada para identificar una serie dada de problemas capaces de ser resueltos en el tiempo en una máquina de Turing determinista?
Por ejemplo, el conjunto de problemas solucionables dentro del tiempo f (n) en una máquina de Turing determinista se denota entonces por DTIME (f (n)) .
Para una definición precisa de lo que significa resolver un problema usando una determinada cantidad de tiempo y espacio, se utiliza un modelo computacional como la máquina de Turing determinista. El tiempo requerido por una máquina de Turing determinista M en la entrada x es el número total de transiciones de estado, o pasos, la máquina hace antes de que se detiene y da la respuesta ("sí" o "no"). Se dice que una máquina de Turing M opera dentro del tiempo f (n), si el tiempo requerido por M en cada entrada de longitud n es a lo sumo f (n). Un problema de decisión A puede ser resuelto en tiempo f (n) si existe una máquina de Turing operando en tiempo f (n) que resuelve el problema. Dado que la teoría de la complejidad está interesada en clasificar problemas basados en su dificultad, se definen conjuntos de problemas basados en algunos criterios. Por ejemplo, el conjunto de problemas solucionables dentro del tiempo f (n) en una máquina de Turing determinista se denota entonces por DTIME (f (n)).
Por ejemplo, el conjunto de problemas solucionables dentro del tiempo f (n) en una máquina de Turing determinista se denota entonces por <hl> DTIME (f (n)) <hl> .
Para una definición precisa de lo que significa resolver un problema usando una determinada cantidad de tiempo y espacio, se utiliza un modelo computacional como la máquina de Turing determinista. El tiempo requerido por una máquina de Turing determinista M en la entrada x es el número total de transiciones de estado, o pasos, la máquina hace antes de que se detiene y da la respuesta ("sí" o "no"). Se dice que una máquina de Turing M opera dentro del tiempo f (n), si el tiempo requerido por M en cada entrada de longitud n es a lo sumo f (n). Un problema de decisión A puede ser resuelto en tiempo f (n) si existe una máquina de Turing operando en tiempo f (n) que resuelve el problema. Dado que la teoría de la complejidad está interesada en clasificar problemas basados en su dificultad, se definen conjuntos de problemas basados en algunos criterios. Por ejemplo, el conjunto de problemas solucionables dentro del tiempo f (n) en una máquina de Turing determinista se denota entonces por <hl> DTIME (f (n)) <hl>.
Para una definición precisa de lo que significa resolver un problema usando una determinada cantidad de tiempo y espacio, se utiliza un modelo computacional como la máquina de Turing determinista. El tiempo requerido por una máquina de Turing determinista M en la entrada x es el número total de transiciones de estado, o pasos, la máquina hace antes de que se detiene y da la respuesta ("sí" o "no"). Se dice que una máquina de Turing M opera dentro del tiempo f (n), si el tiempo requerido por M en cada entrada de longitud n es a lo sumo f (n). Un problema de decisión A puede ser resuelto en tiempo f (n) si existe una máquina de Turing operando en tiempo f (n) que resuelve el problema. Dado que la teoría de la complejidad está interesada en clasificar problemas basados en su dificultad, se definen conjuntos de problemas basados en algunos criterios. <hl> Por ejemplo, el conjunto de problemas solucionables dentro del tiempo f (n) en una máquina de Turing determinista se denota entonces por DTIME (f (n)) . <hl>