P (complejidad)
En la teoría de la complejidad computacional , P , también conocida como PTIME o DTIME ( n O(1) ), es una clase de complejidad fundamental . Contiene todos los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista utilizando una cantidad polinomial de tiempo de cálculo , o tiempo polinomial .
La tesis de Cobham sostiene que P es la clase de problemas computacionales que son "eficientemente solucionables" o " tratables ". Esto es inexacto: en la práctica, algunos problemas que no se sabe que están en P tienen soluciones prácticas, y algunos que están en P no, pero esta es una regla general útil .
P también puede verse como una familia uniforme de circuitos booleanos . Un lenguaje L está en P si y solo si existe una familia de circuitos booleanos uniforme en tiempo polinomial , tal que
La definición del circuito se puede debilitar para usar solo una familia uniforme de espacio de registro sin cambiar la clase de complejidad.
Se sabe que P contiene muchos problemas naturales, incluidas las versiones de decisión de la programación lineal y la búsqueda de una coincidencia máxima . En 2002, se demostró que el problema de determinar si un número es primo está en P. [1] La clase relacionada de problemas de funciones es FP .
Varios problemas naturales están completos para P, incluida la conectividad st (o accesibilidad ) en gráficos alternos. [2] El artículo sobre problemas P-completos enumera otros problemas relevantes en P.