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 resolverse mediante 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 "resolubles eficientemente" 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 sí están en P no, pero ésta 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 en tiempo polinómico en todas las entradas
Para todo x en L , M genera 1
Para todos los x que no están en L , M genera 0

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

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

La definición del circuito se puede debilitar para utilizar sólo 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 funciones es FP .

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

Relaciones con otras clases

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 . De manera equivalente, es la clase de problemas de decisión en la que cada instancia de "sí" tiene un certificado de tamaño polinomial, y los certificados pueden verificarse mediante una máquina de Turing determinista de tiempo polinomial. La clase de problemas para los cuales esto es cierto para los casos de "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 . ${\mathsf {P}}\subsetneq {\mathsf {NP}}$ ${\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 éste 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 que se pueden resolver en memoria logarítmica alternando máquinas de Turing . 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: $O(\log n)$ $2^{O(\log n)}=n^{O(1)}$

{\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, sólo se conocen dos contenciones estrictas:

P está estrictamente contenido en EXPTIME. En consecuencia, todos los problemas difíciles de EXPTIME se encuentran fuera de P, y al menos una de las contenciones a la derecha de P anterior es estricta (de hecho, se cree ampliamente que las tres son estrictas).
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 ú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 grande que contiene casi todos los problemas prácticos, incluido todo BPP . Si contiene NP, entonces la jerarquía polinómica colapsa al segundo nivel. Por otro lado, también contiene algunos problemas poco prá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 sea P-completo, entonces L = P. ^[5]

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 polinómico suponiendo que las llamadas a funciones son de tiempo constante, y si esas funciones llamadas requieren tiempo polinómico, entonces todo el algoritmo toma tiempo polinómico. Una consecuencia de esto es que P es bajo en sí mismo. Esta es también una de las razones principales por las que se considera que P es una clase independiente de la máquina; cualquier "característica" de la máquina, como el acceso aleatorio , que pueda simularse en tiempo polinómico puede simplemente componerse con el algoritmo principal de tiempo polinómico para reducirlo a un algoritmo de tiempo polinómico 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 toroide; Además, Robertson y Seymour demostraron que existe un algoritmo O ( n ³ ) para determinar si un gráfico tiene un gráfico dado como menor. Esto produce una prueba no constructiva de que existe un algoritmo de tiempo polinomial para determinar si un gráfico determinado puede incrustarse en un toro, a pesar de que no se conoce ningún algoritmo concreto para este problema.

Caracterizaciones alternativas

En complejidad descriptiva , P puede describirse como los problemas expresables en FO(LFP) , la lógica de primer orden con un operador de punto mínimo agregado, en 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 se puede definir 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 polinómico automáticamente da un algoritmo polinomial para el problema de decisión correspondiente) . En ese caso P no es un subconjunto de NP, pero P∩DEC sí lo es, donde DEC es la clase de problemas de decisión.

Historia

Kozen ^[12] afirma que a Cobham y Edmonds "generalmente se les atribuye la invención de la noción de tiempo polinómico". Cobham inventó la clase como una forma sólida de caracterizar algoritmos eficientes, lo que llevó a la tesis de Cobham . Sin embargo, HC Pocklington , en un artículo de 1910, ^[13]^[14] 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 otro que tomaba tiempo proporcional "al módulo mismo o su raíz cuadrada", estableciendo así explícitamente una distinción entre un algoritmo que se ejecutó en tiempo polinómico y uno que no lo hizo.

Notas

^ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES está en P", Annals of Mathematics 160 (2004), no. 2, págs. 781–793.
^ Immerman, Neil (1999). Complejidad Descriptiva . Nueva York: Springer-Verlag. ISBN 978-0-387-98600-5.
^ Johnsonbaugh, Richard F .; Schaefer, Marcos (2004). Algoritmos . Educación Pearson. pag. 458.ISBN 0-02-360692-4.
^ "teoría de la complejidad: ¿por qué co-P = P?". Desbordamiento de pila . Archivado desde el original el 14 de octubre de 2020 . Consultado el 14 de octubre de 2020 .
^ 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 .
^ Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). Introducción a la teoría, los lenguajes y la computación de los autómatas (2. ed.). Boston: Addison-Wesley. págs. 425–426. ISBN 978-0201441246.
^ Immerman, Neil (1999). Complejidad Descriptiva . Nueva York: Springer-Verlag. pag. 66.ISBN 978-0-387-98600-5.
^ Vardi, Moshe Y. (1982). "La complejidad de los lenguajes de consulta relacionales". STOC '82: Actas del decimocuarto simposio anual de ACM sobre teoría de la informática . págs. 137-146. doi : 10.1145/800070.802186.
^ Immerman, Neil (1982). "Consultas relacionales computables en tiempo polinómico". STOC '82: Actas del decimocuarto simposio anual de ACM sobre teoría de la informática . págs. 147-152. doi : 10.1145/800070.802187. Versión revisada en Información y Control , 68 (1986), 86–104.
^ Laura Kallmeyer (2010). Análisis más allá de las gramáticas libres de contexto . Medios de ciencia y negocios de Springer. págs.5 y 37. ISBN 978-3-642-14846-0.citando http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf como prueba
^ Wegener, Ingo (2005). Teoría de la Complejidad . Springer-Verlag. pag. 35.doi : 10.1007 /3-540-27477-4. ISBN 978-3-540-21045-0.
^ Kozen, Dexter C. (2006). Teoría de la Computación . Saltador. pag. 4.ISBN 978-1-84628-297-3.
^ Pocklington, HC (1910-1912). "La determinación del exponente al que pertenece un número, la solución práctica de determinadas congruencias y la ley de reciprocidad cuadrática". Proc. Camb. Fil. Soc . 16 : 1–5.
^ 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 al 13 de agosto de 1993, Vancouver, Columbia Británica . Providence, RI: Sociedad Estadounidense de Matemáticas. págs. 503–504. ISBN 978-0-8218-0291-5.

Referencias

Cobham, Alan (1965). "La dificultad computacional intrínseca de las funciones". Proc. Lógica, Metodología y Filosofía de la Ciencia II . Holanda del Norte.
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 polinómico, págs. 971–979.
Papadimitriou, Christos H. (1994). Complejidad computacional . Lectura, Massachusetts: Addison – Wesley. ISBN 978-0-201-53082-7.
Sipser, Michael (2006). Introducción a la Teoría de la Computación, 2ª Edición . Curso Tecnología Inc. ISBN 978-0-534-95097-2.Sección 7.2: La Clase P, págs. 256–263;

enlaces externos

Zoológico de Complejidad : Clase P
Zoológico de complejidad : Clase P/poli