P (clase de complejidad)

En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor o igual que un cierto valor 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 tiempo polinómico P. La tesis de Cobham postula que la clase P es la que tiene los problemas tratables más grandes, es decir, los problemas de gran tamaño que se pueden calcular de forma eficiente con un ordenador.

Por ejemplo, si determinar el camino óptimo que debe recorrer un cartero que pasa por ${\displaystyle N}$ casas necesita menos de ${\displaystyle 50N^{2}+N}$ segundos, entonces el problema es resoluble en un "tiempo polinómico".

De esa manera, tiempos de ${\displaystyle 2n^{2}+5n}$, ${\displaystyle 4n^{6}+7n^{4}-2n^{2}}$ o ${\displaystyle n^{2^{2^{175}}}}$ son polinómicos; pero ${\displaystyle 2^{n}}$ no lo es.

Dentro de los tiempos polinómicos, podemos distinguir los logarítmicos ${\displaystyle O(\log n)}$, los lineales ${\displaystyle O(n)}$, los cuadráticos ${\displaystyle O(n^{2})}$, los cúbicos ${\displaystyle O(n^{3})}$, etc.