P (complejidad) - P (complexity)

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 usando 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 "solucionables de manera eficiente" o " manejables ". 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 práctica útil .

Definición

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

  • M se ejecuta por tiempo polinomial en todas las entradas
  • Para todas las x en L , M salidas 1
  • Para todas las x no en L , M salidas 0

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 uniforme de circuitos booleanos en tiempo polinómico , tal que

  • Para todos , toma n bits como entrada y salidas 1 bit
  • Para todo x en L ,
  • Para todo x no en L ,

La definición del circuito se puede debilitar para usar solo una familia de uniformes de espacio de registro 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. La clase relacionada de problemas de función es FP .

Varios problemas naturales están completos para P, incluida la conectividad st (o accesibilidad ) en gráficos alternos. El artículo sobre problemas P-complete enumera otros problemas relevantes en P.

Relaciones con otras clases

Una generalización de P es NP , que es la clase de problemas de decisión que puede decidir una máquina de Turing no determinista que se ejecuta en tiempo polinomial . De manera equivalente, 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 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, aunque esto (la hipótesis ) no se ha probado. Otro problema abierto es si NP = co-NP; dado que P = co-P, una respuesta negativa implicaría .

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 usa el espacio no puede usar más que el tiempo, porque este es el número total de configuraciones posibles; por 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 la 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 polinómico. Nuevamente, si P = PSPACE es un problema abierto. Para resumir:

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

  • P está estrictamente contenido en EXPTIME. En consecuencia, todos los problemas EXPTIME-hard se encuentran fuera de P, y al menos una de las contención 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 / poli , o polinomio-tiempo no uniforme. Si un problema está en P / poly, entonces se puede resolver en un 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, incluidos todos los de BPP . Si contiene NP, entonces la jerarquía polinomial 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 escaso que es P-completo, entonces L = P.

Propiedades

Los algoritmos de tiempo polinómico 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 esas funciones llamadas en sí mismas requieren tiempo polinomial, entonces todo el algoritmo toma tiempo polinomial. Una consecuencia de esto es que P es bajo en 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 pueda simular en tiempo polinomial, simplemente se puede 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 .

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 gráficos que se pueden incrustar en un toro; además, Robertson y Seymour demostraron que existe un algoritmo O ( n 3 ) 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 dado se puede incrustar en un toro, a pesar de que no se conoce ningún algoritmo concreto para este problema.

Caracterizaciones alternativas

En complejidad descriptiva , P se puede describir como los problemas expresables en FO (LFP) , la lógica de primer orden con un operador de punto fijo mínimo agregado, en estructuras ordenadas. En el libro de texto de Immerman de 1999 sobre complejidad descriptiva , Immerman atribuye este resultado a Vardi e Immerman.

Se publicó en 2001 que PTIME corresponde a gramáticas de concatenación de rangos (positivos) .

Historia

Kozen afirma que a Cobham y Edmonds "generalmente se les atribuye la invención de la noción de tiempo polinomial". 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, analizó dos algoritmos para resolver congruencias cuadráticas, y observó que uno tomaba tiempo "proporcional a una potencia del logaritmo del módulo" y lo contrastaba con uno que tomaba tiempo proporcional "al módulo mismo. o su raíz cuadrada ", trazando así explícitamente una distinción entre un algoritmo que se ejecutó en tiempo polinomial y uno que no lo hizo.

Notas

Referencias

enlaces externos