Turing de una sola cinta
question: Un lenguaje resuelto en tiempo cuadrático implica el uso de qué tipo de máquina de Turing?, 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.
Un lenguaje resuelto en tiempo cuadrático implica el uso de qué tipo de máquina de Turing?
de Turing de una sola cinta .
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.
de <hl> Turing de una sola cinta <hl> .
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 <hl> Turing de una sola cinta <hl>. 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 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 <hl> de Turing de una sola cinta . <hl> 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.