modelo de máquina
question: El límite concreto de tiempo de computación con frecuencia produce clases de complejidad dependientes de qué?, context: Pero limitar el tiempo de cálculo anterior por alguna función concreta f (n) a menudo produce clases de complejidad que dependen del modelo de máquina elegido. Por ejemplo, el lenguaje {xx. X es cualquier cadena binaria} se puede resolver en tiempo lineal en una máquina de Turing multi-cinta, pero necesariamente requiere tiempo cuadrático en el modelo de máquinas de Turing de una sola cinta. Si permitimos variaciones polinómicas en tiempo de ejecución, la tesis de Cobham-Edmonds establece que "las complejidades de tiempo en dos modelos razonables y generales de computación están relacionadas polinomialmente" (Goldreich, 2008). Esto forma la base para la clase de complejidad P, que es el conjunto de problemas de decisión resolubles por una máquina de Turing determinista dentro del tiempo polinómico. El conjunto correspondiente de problemas de función es FP.
El límite concreto de tiempo de computación con frecuencia produce clases de complejidad dependientes de qué?
del modelo de máquina elegido.
Pero limitar el tiempo de cálculo anterior por alguna función concreta f (n) a menudo produce clases de complejidad que dependen del modelo de máquina elegido. Por ejemplo, el lenguaje {xx. X es cualquier cadena binaria} se puede resolver en tiempo lineal en una máquina de Turing multi-cinta, pero necesariamente requiere tiempo cuadrático en el modelo de máquinas de Turing de una sola cinta. Si permitimos variaciones polinómicas en tiempo de ejecución, la tesis de Cobham-Edmonds establece que "las complejidades de tiempo en dos modelos razonables y generales de computación están relacionadas polinomialmente" (Goldreich, 2008). Esto forma la base para la clase de complejidad P, que es el conjunto de problemas de decisión resolubles por una máquina de Turing determinista dentro del tiempo polinómico. El conjunto correspondiente de problemas de función es FP.
del <hl> modelo de máquina <hl> elegido.
Pero limitar el tiempo de cálculo anterior por alguna función concreta f (n) a menudo produce clases de complejidad que dependen del <hl> modelo de máquina <hl> elegido. Por ejemplo, el lenguaje {xx. X es cualquier cadena binaria} se puede resolver en tiempo lineal en una máquina de Turing multi-cinta, pero necesariamente requiere tiempo cuadrático en el modelo de máquinas de Turing de una sola cinta. Si permitimos variaciones polinómicas en tiempo de ejecución, la tesis de Cobham-Edmonds establece que "las complejidades de tiempo en dos modelos razonables y generales de computación están relacionadas polinomialmente" (Goldreich, 2008). Esto forma la base para la clase de complejidad P, que es el conjunto de problemas de decisión resolubles por una máquina de Turing determinista dentro del tiempo polinómico. El conjunto correspondiente de problemas de función es FP.
Pero limitar el tiempo de cálculo anterior por alguna función concreta f (n) a menudo produce clases de complejidad que dependen <hl> del modelo de máquina elegido. <hl> Por ejemplo, el lenguaje {xx. X es cualquier cadena binaria} se puede resolver en tiempo lineal en una máquina de Turing multi-cinta, pero necesariamente requiere tiempo cuadrático en el modelo de máquinas de Turing de una sola cinta. Si permitimos variaciones polinómicas en tiempo de ejecución, la tesis de Cobham-Edmonds establece que "las complejidades de tiempo en dos modelos razonables y generales de computación están relacionadas polinomialmente" (Goldreich, 2008). Esto forma la base para la clase de complejidad P, que es el conjunto de problemas de decisión resolubles por una máquina de Turing determinista dentro del tiempo polinómico. El conjunto correspondiente de problemas de función es FP.