Clase P

En la teoría de los algoritmos, la clase P (del inglés  polynomio ) es un conjunto de problemas para los cuales existen algoritmos de solución “rápida” (cuyo tiempo de ejecución depende polinomialmente del tamaño de los datos de entrada). La clase P está incluida en clases de algoritmos de complejidad más amplia.

Definiciones

Formal definición

El algoritmo se identifica con una máquina de Turing determinista que calcula la respuesta dada una palabra del alfabeto de entrada dado a la cinta de entrada . El tiempo de ejecución del algoritmo para una palabra de entrada fija x es el número de ciclos de trabajo de la máquina de Turing desde el inicio hasta la parada de la máquina. La complejidad de una función calculada por alguna máquina de Turing es una función que depende de la longitud de la palabra de entrada y es igual al tiempo máximo de funcionamiento de la máquina sobre todas las palabras de entrada de una longitud fija:

Si para una función f existe una máquina de Turing M tal que para algún número c y n suficientemente grande , entonces se dice que pertenece a la clase P, o es polinomial en el tiempo.

De acuerdo con la tesis de Church-Turing , cualquier algoritmo concebible puede implementarse en una máquina de Turing. Para cualquier lenguaje de programación, puede definir una clase P de manera similar (reemplazando la máquina de Turing en la definición con una implementación del lenguaje de programación). Si el compilador del lenguaje en el que se implementa el algoritmo ralentiza polinomialmente la ejecución del algoritmo (es decir, el tiempo de ejecución del algoritmo en una máquina de Turing es menor que algún polinomio de su tiempo de ejecución en un lenguaje de programación), entonces las definiciones de clases P para este lenguaje y para la máquina de Turing son las mismas. El código del lenguaje ensamblador se puede convertir a una máquina de Turing con un poco de desaceleración polinomial, y dado que todos los lenguajes existentes permiten la compilación a ensamblador (nuevamente, con desaceleración polinomial), las definiciones de la clase P para máquinas de Turing y para cualquier lenguaje de programación existente son lo mismo.

Una definición más estrecha

A veces, la clase P significa una clase más estrecha de funciones, a saber, la clase de predicados (funciones ). En este caso, la lengua L , que se reconoce por este predicado, es el conjunto de palabras sobre las que el predicado es igual a 1. Las lenguas de la clase P son las lenguas para las que hay predicados de la clase P que los reconocen Es obvio que si los lenguajes y pertenecen a la clase P, entonces su unión, intersección y complementos también pertenecen a la clase P.

Inclusiones de la clase P en otras clases

La clase P es una de las clases de complejidad más limitada. Los algoritmos que le pertenecen también pertenecen a la clase NP , la clase BPP (ya que permiten una implementación polinomial con error cero), la clase PSPACE (porque el área de trabajo en una máquina de Turing es siempre menor que el tiempo), la clase P/Poly (para probar este hecho, se utiliza el concepto de protocolo de la máquina, que se convierte en un esquema booleano de tamaño polinomial).

Durante más de 30 años, el problema de la igualdad de las clases P y NP ha permanecido sin resolver . Si son iguales, cualquier problema de la clase NP se puede resolver rápidamente (en tiempo polinomial). Sin embargo, la comunidad científica se inclina hacia la respuesta negativa a esta pregunta. Además, no se ha probado el rigor de la inclusión en clases más amplias, por ejemplo, en PSPACE, pero la igualdad de P y PSPACE parece muy dudosa en este momento.

Ejemplos de problemas

Problemas pertenecientes a la clase P

Ejemplos de problemas de la clase P son la suma de enteros, la multiplicación, la división, tomar el resto de la división, la multiplicación de matrices , encontrar la conexión de los gráficos , ordenar un conjunto de n números, encontrar un ciclo de Euler en un gráfico de m aristas, encontrar algunos palabra en un texto de longitud n, construyendo una cubierta de árboles de costo mínimo, programación lineal, y algunos otros.

Problemas cuya pertenencia a la clase P es desconocida

Hay muchos problemas para los que no se ha encontrado un algoritmo polinomial, pero no se ha probado que no exista. En consecuencia, no se sabe si tales problemas pertenecen a la clase P. Estos son algunos de ellos:

1. El problema del viajante de comercio (así como todos los demás problemas NP-completos ). La solución polinómica de este problema equivale a establecer la igualdad de las clases P y NP .
2. Descomposición de un número en factores primos .
3. Logaritmo discreto en un campo finito .
4. Problema de subgrupos ocultos con n generadores.
5. Logaritmo discreto en un grupo aditivo de puntos en una curva elíptica .

Valor práctico

Dado que a menudo es necesario calcular los valores de las funciones en grandes datos de entrada, encontrar algoritmos polinómicos para calcular funciones es una tarea muy importante. Se cree que es mucho más difícil calcular funciones que no pertenecen a la clase P que aquellas que sí. La mayoría de los algoritmos de la clase P tienen una complejidad que no supera un polinomio de grado pequeño sobre el tamaño de los datos de entrada. Por ejemplo, el algoritmo estándar de multiplicación de matrices requiere n 3 multiplicaciones (aunque existen algoritmos más rápidos, como el algoritmo de Strassen ). El grado de un polinomio rara vez es grande. Uno de esos casos es la prueba Agrawal-Kayala-Saksena propuesta en 2002 por matemáticos indios , que descubre si el número n es primo en operaciones O (log 6 n ).

Literatura

• Thomas H. Kormen y otros Algoritmos: Construcción y análisis = Introducción a los algoritmos. - 2ª ed. - M. : "Williams" , 2006. - 1296 p. — ISBN 0-07-013151-1 .
• John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducción a la teoría de autómatas, lenguajes y computación. - M. : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .

Enlaces