¿Qué significa "problema de tiempo polinomial"?

El tiempo polinómico es relativo al tiempo exponencial. Supongamos que la escala del problema es N, entonces, si la complejidad temporal del algoritmo es T(N)=aN^k1 + bN^k2 + cN^k3+. .. .+xN^kx+... donde k1>k2>k3... y es una constante definida, y a, b, c... también son constantes, es decir, T (N) es un polinomio de N , que se llama El problema (algoritmo) tiene tiempo polinomial.

Lo opuesto es el tiempo exponencial, es decir, T(N)=ax^N, donde a es una constante y x también es una constante, lo que se llama tiempo exponencial.