clase de complejidad P
question: Los problemas de decisión capaces de ser resueltos por una máquina de Turing determinista mientras se mantiene la adhesión al tiempo polinomial pertenecen a qué clase?, 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.
Los problemas de decisión capaces de ser resueltos por una máquina de Turing determinista mientras se mantiene la adhesión al tiempo polinomial pertenecen a qué clase?
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.
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.
la <hl> clase de complejidad P <hl> , que es el conjunto de problemas de decisión resolubles por una máquina de Turing determinista dentro del tiempo polinómico.
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 <hl> clase de complejidad P <hl>, 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 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 <hl> 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. <hl> El conjunto correspondiente de problemas de función es FP.