vald
Problema p
En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor que unciertovalor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempopolinómico.Por ejemplo, si determinar el camino óptimo que debe recorrer un cartero que pasa por N casas necesita menos de 50N2+N segundos, entonces el problema es resoluble en un "tiempo polinómico".
Deesamanera, tiempos de 2n2+5n, o 4n6+7n4-2n2 son polinómicos; pero 2n no lo es.
Dentro de los tiempos polinómicos, podemos distinguir los logarítmicos (log(n)), los lineales (n), los cuadráticos (n2),cúbicos(n3), etc.
Clases de complejidad
En teoría de la complejidad, la clase de complejidad de los problemas de decisión que pueden ser resueltos en tiempo polinómico calculado a partir de la entradaporuna máquina de Turing determinista es llamada P. Cuando se trata de una máquina de Turing no-determinista, la clase se llama NP. Una de las preguntas abiertas más importantes en la actualidad...
Regístrate para leer el documento completo.