P (complejidad)

Clase de problemas resolubles en tiempo polinomial

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 resolverse mediante una máquina de Turing determinista utilizando una cantidad polinómica de tiempo de cálculo , o tiempo polinómico .

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 otros que sí están en P no las tienen, pero esta es una regla práctica útil .

Definición

Un lenguaje L está en P si y sólo si existe una máquina de Turing determinista M , tal que

• M se ejecuta durante un tiempo polinomial en todas las entradas
• Para todo x en L , M da como resultado 1
• Para todos los x no en L , M da como resultado 0

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

• Para todos , toma n bits como entrada y genera 1 bit como salida ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle C_{n}}$
• Para todo x en L , ${\displaystyle C_{|x|}(x)=1}$
• Para todo x no en L , ${\displaystyle C_{|x|}(x)=0}$

La definición del circuito se puede debilitar para utilizar solo una familia uniforme de espacio logarítmico sin cambiar la clase de complejidad.

Problemas notables en P

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 función es FP .

Varios problemas naturales son completos para P, incluida la st -conectividad (o alcanzabilidad ) en gráficos alternados. ^[2] El artículo sobre problemas P-completos enumera otros problemas relevantes en P.

Relaciones con otras clases

Una representación de la relación entre clases de complejidad.

Inclusiones de clases de complejidad que incluyen P, NP , co-NP , BPP , P/poly , PH y PSPACE

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 en tiempo polinomial. La clase de problemas para los que 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 adecuado, ^[3] aunque esta creencia (la hipótesis) sigue sin demostrarse . 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}}}$ ${\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 espacio no puede utilizar más que 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 el espacio polinomial. Nuevamente, si P = PSPACE es un problema abierto. Para resumir: ${\displaystyle O(\log n)}$ ${\displaystyle 2^{O(\log n)}=n^{O(1)}}$

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

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

• P está estrictamente contenido en EXPTIME. En consecuencia, todos los problemas que requieren EXPTIME se encuentran fuera de P, y al menos uno de los contenidos a la derecha de P es estricto (de hecho, se cree ampliamente que los tres son estrictos).
• 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 está en P/poly, entonces se puede resolver en tiempo polinomial determinista siempre que se proporcione una cadena de consejos que dependa solo 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 grande que contiene casi todos los problemas prácticos, incluido todo BPP . Si contiene NP, entonces la jerarquía polinomial colapsa al segundo nivel. Por otro lado, también contiene algunos problemas imprácticos, incluidos 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 en relación con las clases de complejidad probabilística ( ZPP , RP , co-RP, BPP , BQP , PP ), todas dentro de PSPACE . Se desconoce si alguna de estas contenciones es estricta.

P está contenido en BQP , se desconoce si la contención es estricta.

Propiedades

Los algoritmos de tiempo polinomial están cerrados bajo composición. Intuitivamente, esto dice que si uno escribe una función que es de tiempo polinomial asumiendo que las llamadas de función son de tiempo constante, y si las funciones llamadas requieren tiempo polinomial, entonces todo el algoritmo toma tiempo polinomial. Una consecuencia de esto es que P es bajo para sí mismo. 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 se puede simular en tiempo polinomial se puede simplemente componer 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 están cerrados bajo inversión, intersección , unión , concatenación , cierre de Kleene , homomorfismo inverso y complementación . ^[6]

Pruebas de existencia pura de algoritmos de tiempo polinomial

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 produce una prueba no constructiva de que existe un algoritmo en tiempo polinomial para determinar si un grafo dado se puede incrustar en un toro, a pesar del hecho de que no se conoce ningún algoritmo concreto para este problema.

Caracterizaciones alternativas

En la 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 agregado, 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. ^[9]

En 2001 se publicó que PTIME corresponde a gramáticas de concatenación de rangos (positivos) . ^[10]

P también puede definirse como una clase de complejidad algorítmica para problemas que no son problemas de decisión ^[11] (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 que P∩DEC lo es, donde DEC es la clase de problemas de decisión.

Historia

Kozen ^[12] afirma que a Cobham y Edmonds "se les atribuye generalmente la invención de la noción de tiempo polinomial", aunque Rabin también inventó la noción de forma independiente y aproximadamente en la misma época (el artículo de Rabin ^[13] estaba en las actas de una conferencia de 1966 en 1967, mientras que el de Cobham ^[14] estaba en las actas de una conferencia de 1964 en 1965 y el de Edmonds ^[15] se publicó en una revista en 1965, aunque Rabin no menciona a ninguno de ellos y aparentemente no estaba al tanto de ellos). 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, ^{[16] [17]} 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 lo contrastó con uno que tomaba un tiempo proporcional "al módulo mismo o su raíz cuadrada", trazando así explícitamente una distinción entre un algoritmo que se ejecutaba en tiempo polinomial versus uno que se ejecutaba en tiempo (moderadamente) exponencial.

Notas

1. Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES está en P", Annals of Mathematics 160 (2004), no. 2, págs. 781–793.
2. Immerman, Neil (1999). Complejidad descriptiva . Nueva York: Springer-Verlag. ISBN 978-0-387-98600-5.
3. Johnsonbaugh, Richard F .; Schaefer, Marcus (2004). Algoritmos . Pearson Education. pág. 458. ISBN 0-02-360692-4.
4. "Teoría de la complejidad: ¿Por qué co-P = P?". Stack Overflow . Archivado desde el original el 14 de octubre de 2020 . Consultado el 14 de octubre de 2020 .
5. Cai, Jin-Yi ; Sivakumar, D. (abril de 1999). "Conjuntos duros dispersos para P: Resolución de una conjetura de Hartmanis". Revista de Ciencias de la Computación y de Sistemas . 58 (2): 280–296. doi : 10.1006/jcss.1998.1615 .
6. Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). Introducción a la teoría de autómatas, lenguajes y computación (2. ed.). Boston: Addison-Wesley. págs. 425–426. ISBN 978-0201441246.
7. Immerman, Neil (1999). Complejidad descriptiva . Nueva York: Springer-Verlag. pág. 66. ISBN. 978-0-387-98600-5.
8. Vardi, Moshe Y. (1982). "La complejidad de los lenguajes de consulta relacionales". STOC '82: Actas del decimocuarto simposio anual de la ACM sobre teoría de la computación . págs. 137–146. doi :10.1145/800070.802186.
9. Immerman, Neil (1982). "Consultas relacionales computables en tiempo polinomial". STOC '82: Actas del decimocuarto simposio anual de la ACM sobre teoría de la computación . págs. 147–152. doi :10.1145/800070.802187. Versión revisada en Información y Control , 68 (1986), 86–104.
10. Laura Kallmeyer (2010). Análisis más allá de las gramáticas libres de contexto . Springer Science & Business Media. Págs. 5 y 37. ISBN. 978-3-642-14846-0.citando http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf para la prueba
11. Wegener, Ingo (2005). Teoría de la complejidad . Springer-Verlag. pág. 35. doi :10.1007/3-540-27477-4. ISBN. 978-3-540-21045-0.
12. Kozen, Dexter C. (2006). Teoría de la Computación . Saltador. pag. 4.ISBN​ 978-1-84628-297-3.
13. Rabin, Michael O. (1967). "Teoría matemática de los autómatas". Aspectos matemáticos de la informática. Proc. Sympos. Appl. Math., vol. XIX . Amer. Math. Soc., págs. 153-175.
14. Cobham, Alan (1965). "La dificultad computacional intrínseca de las funciones". Lógica, metodología y filosofía. (Proc. 1964 Internat. Congr.) . pp. 24–30.
15. Edmonds, J. (1965). "Caminos, árboles y flores". Canadian J. Math . 17 : 449–467. doi :10.4153/CJM-1965-045-4.
16. Pocklington, HC (1910–1912). "La determinación del exponente al que pertenece un número, la solución práctica de ciertas congruencias y la ley de reciprocidad cuadrática". Proc. Camb. Phil. Soc . 16 : 1–5.
17. Gautschi, Walter (1994). Matemáticas de la computación, 1943-1993: medio siglo de matemáticas computacionales: Simposio del 50.° aniversario de Matemáticas de la computación, 9-13 de agosto de 1993, Vancouver, Columbia Británica . Providence, RI: American Mathematical Society. pp. 503-504. ISBN 978-0-8218-0291-5.

Referencias

• Edmonds, J. (1965). "Caminos, árboles y flores". Canadian J. Math . 17 : 449–467. doi :10.4153/CJM-1965-045-4.
• Cobham, Alan (1965). "La dificultad computacional intrínseca de las funciones". Proc. Lógica, metodología y filosofía de la ciencia II 1964. Holanda del Norte.
• Rabin, Michael O. (1967). "Teoría matemática de los autómatas". Aspectos matemáticos de la informática. Proc. 1966 Sympos. Appl. Math., vol. XIX . Amer. Math. Soc. págs. 153–175.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw–Hill, 2001. ISBN 0-262-03293-7 . Sección 34.1: Tiempo polinomial, págs. 971–979. 
• Papadimitriou, Christos H. (1994). Complejidad computacional . Reading, Mass.: Addison–Wesley. ISBN 978-0-201-53082-7.
• Sipser, Michael (2006). Introducción a la teoría de la computación, 2.ª edición . Course Technology Inc. ISBN 978-0-534-95097-2.Sección 7.2: La Clase P, págs. 256–263;.

Enlaces externos

• Zoológico de la complejidad : Clase P
• Zoológico de la complejidad : clase P/poli