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 polinómica de tiempo de computación , o tiempo polinomial .

La tesis de Cobham sostiene que P es la clase de problemas computacionales que son "eficientemente resolubles" o " tratables ". Esto es inexacto: en la práctica, algunos problemas que no se sabe que pertenecen a P tienen soluciones prácticas, y algunos que sí pertenecen a P no las tienen, pero esta es una regla general útil .

Un lenguaje L está en P si y solo si existe una máquina de Turing determinista M tal que

• M se ejecuta en tiempo polinomial en todas las entradas.
• Para todo x en L , M produce 1
• Para todo x que no pertenece a L , M produce 0.

P también puede considerarse como una familia uniforme de circuitos booleanos . Un lenguaje L pertenece a P si y solo si existe una familia uniforme de circuitos booleanos de tiempo polinomial.${\displaystyle \{C_{n}:n\in \mathbb {N} \}}$, de tal manera que

• A pesar de${\displaystyle n\in \mathbb {N} }$,${\displaystyle C_{n}}$Recibe n bits como entrada y produce 1 bit como salida.
• Para todo x en L ,${\displaystyle C_{|x|}(x)=1}$
• Para todo x que no está en L ,${\displaystyle C_{|x|}(x)=0}$

La definición del circuito se puede debilitar para usar solo una familia uniforme de espacio logarítmico 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 encontrar un emparejamiento máximo . 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 son completos para P, incluyendo la st- conectividad (o alcanzabilidad ) en grafos alternantes ^{[ 2 ].} El artículo sobre problemas P-completos enumera otros problemas relevantes en P.

Una generalización de P es NP , que es la clase de problemas de decisión decidibles por una máquina de Turing no determinista que se ejecuta en tiempo polinomial . Equivalentemente, es la clase de problemas de decisión donde cada instancia "sí" tiene un certificado de tamaño polinomial, y los certificados pueden ser verificados por una máquina de Turing determinista de tiempo polinomial. La clase de problemas para los cuales esto es cierto para las instancias "no" se llama co-NP . P es trivialmente un subconjunto de NP y de co-NP; la mayoría de los expertos creen que es un subconjunto propio, ^{[ 3 ]} aunque esta creencia (la${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$La hipótesis) sigue sin probarse . Otro problema abierto es si NP  =  co-NP; dado que P = co-P, ^{[ 4 ]} una respuesta negativa implicaría${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$.

También se sabe que P es al menos tan grande como L , la clase de problemas decidibles en una cantidad logarítmica de espacio de memoria . Un decisor que utiliza${\displaystyle O(\log n)}$El espacio no puede utilizar más de${\displaystyle 2^{O(\log n)}=n^{O(1)}}$tiempo, porque este es el número total de configuraciones posibles; por lo tanto, L es un subconjunto de P. Otro problema importante es si L = P. Sabemos que P = AL, el conjunto de problemas resolubles en memoria logarítmica mediante máquinas de Turing alternas . También se sabe que P no es mayor que PSPACE , la clase de problemas decidibles en espacio polinomial. PSPACE es equivalente a NPSPACE según el teorema de Savitch . Nuevamente, si P = PSPACE es un problema abierto. En resumen:

${\displaystyle {\mathsf {L}}\subseteq {\mathsf {AL}}={\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {PSPACE}}={\mathsf {NPSPACE}}\subseteq {\mathsf {EXPTIME}}.}$

Aquí, EXPTIME es la clase de problemas que se pueden resolver en tiempo exponencial. De todas las clases mostradas anteriormente, solo se conocen dos contenciones estrictas:

• P está estrictamente contenido en EXPTIME. Por consiguiente, todos los problemas EXPTIME-difíciles quedan fuera de P, y al menos una de las contenciones a la derecha de P mencionadas anteriormente es estricta (de hecho, se cree ampliamente que las tres lo son).
• L está estrictamente contenido en PSPACE.

Los problemas más difíciles en P son los problemas P-completos .

Otra generalización de P es P/poly , o tiempo polinomial no uniforme. Si un problema pertenece a P/poly, puede resolverse en tiempo polinomial determinista siempre que se proporcione una cadena de consejos que dependa únicamente de la longitud de la entrada. Sin embargo, a diferencia de NP, la máquina de tiempo polinomial no necesita detectar cadenas de consejos fraudulentas; no es un verificador. P/poly es una clase amplia que contiene casi todos los problemas prácticos, incluyendo todos los de BPP . Si contiene NP, la jerarquía polinomial se reduce al segundo nivel. Por otro lado, también contiene algunos problemas poco prácticos, incluyendo algunos problemas indecidibles como la versión unaria de cualquier problema indecidible.

En 1999, Jin-Yi Cai y D. Sivakumar, basándose en el trabajo de Mitsunori Ogihara , demostraron que si existe un lenguaje disperso que es P-completo, entonces L = P. ^{[ 5 ]}

P está contenido en BQP ; se desconoce si esta contención es estricta.

Los algoritmos de tiempo polinomial son cerrados bajo composición. Intuitivamente, esto significa que si se escribe una función de tiempo polinomial, suponiendo que las llamadas a funciones son de tiempo constante, y si las funciones llamadas requieren tiempo polinomial, entonces todo el algoritmo se ejecuta en tiempo polinomial. Una consecuencia de esto es que P es de baja complejidad computacional. Esta es también una de las principales razones por las que P se considera una clase independiente de la máquina; cualquier "característica" de la máquina, como el acceso aleatorio , que pueda simularse en tiempo polinomial, puede simplemente combinarse con el algoritmo principal de tiempo polinomial para reducirlo a un algoritmo de tiempo polinomial en una máquina más básica.

Los lenguajes en P también son cerrados bajo inversión, intersección , unión , concatenación , cierre de Kleene , homomorfismo inverso y complementación . ^{[ 6 ]}

Se sabe que algunos problemas se pueden resolver en tiempo polinomial, pero no se conoce ningún algoritmo concreto para resolverlos. Por ejemplo, el teorema ^de Robertson-Seymour garantiza que existe una lista finita de menores prohibidos que caracteriza (por ejemplo) el conjunto de grafos que se pueden incrustar en un toro; además, Robertson y Seymour demostraron que existe un algoritmo O( n³ ) para determinar si un grafo tiene un grafo dado como menor. Esto proporciona una prueba no constructiva de que existe un algoritmo de tiempo polinomial para determinar si un grafo dado se puede incrustar en un toro, a pesar de que no se conoce ningún algoritmo concreto para este problema.

En complejidad descriptiva , P puede describirse como los problemas expresables en FO(LFP) , la lógica de primer orden con un operador de punto fijo mínimo añadido, sobre estructuras ordenadas. En el libro de texto de Immerman de 1999 sobre complejidad descriptiva, ^{[ 7 ]} Immerman atribuye este resultado a Vardi ^{[ 8 ]} y a Immerman 1982. ^{[ 9 ]}

En 1992, Bellantoni y Cook dieron una caracterización alternativa de FP ^{[ 10 ]} , definiendo funciones computables en tiempo polinomial mediante un esquema de recursión seguro, proporcionando una definición estructural independiente de la máquina dentro del marco de la complejidad computacional implícita . ^{[ 11 ]}

En 2001 se publicó que PTIME corresponde a gramáticas de concatenación de rango (positivas) . ^{[ 12 ]}

P también puede definirse como una clase de complejidad algorítmica para problemas que no son problemas de decisión ^{[ 13 ]} (aunque, por ejemplo, encontrar la solución a una instancia de 2-satisfacibilidad en tiempo polinomial automáticamente da un algoritmo polinomial para el problema de decisión correspondiente). En ese caso, P no es un subconjunto de NP, sino${\displaystyle P\cap DEC}$es, donde${\displaystyle DEC}$es la clase de problemas de decisión.

Kozen ^{[ 14 ]} afirma que a Cobham y Edmonds "generalmente se les atribuye la invención de la noción de tiempo polinomial", aunque Rabin también inventó la noción de forma independiente y casi al mismo tiempo (el artículo de Rabin ^{[ 15 ]} fue en las actas de 1967 de una conferencia de 1966, mientras que el de Cobham ^{[ 16 ]} fue en las actas de 1965 de una conferencia de 1964 y el de Edmonds ^{[ 17 ]} se publicó en una revista en 1965, aunque Rabin no hace mención de ninguno de los dos y aparentemente no estaba al tanto de ellos). ^{[ 18 ]} Cobham inventó la clase como una forma robusta de caracterizar algoritmos eficientes, lo que llevó a la tesis de Cobham . Sin embargo, HC Pocklington , en un artículo de 1910, ^{[ 19 ] [ 20 ]} analizó dos algoritmos para resolver congruencias cuadráticas y observó que uno tomaba un tiempo "proporcional a una potencia del logaritmo del módulo" y contrastó esto con otro que tomaba un tiempo proporcional "al módulo mismo o a su raíz cuadrada", estableciendo así explícitamente una distinción entre un algoritmo que se ejecutaba en tiempo polinomial y otro que se ejecutaba en tiempo (moderadamente) exponencial.

• Entrada "Teoría de la complejidad computacional"Por Walter Dean en la Enciclopedia de Filosofía de Stanford , otoño de 2021
• StackOverflow. "Teoría de la complejidad: ¿Por qué co-P = P?" . Stack Overflow . Consultado el 15 de noviembre de 2025 .
• Zoológico de la complejidad : Clase P
• Zoológico de complejidad : Clase P/poly