Tiempo pseudo-polinomial

En la teoría de la complejidad computacional , un algoritmo numérico se ejecuta en tiempo pseudopolinomial si su tiempo de ejecución es un polinomio en el valor numérico de la entrada (el entero más grande presente en la entrada), pero no necesariamente en la longitud de la entrada (la cantidad de bits necesarios para representarla), que es el caso de los algoritmos de tiempo polinomial . ^[1]

En general, el valor numérico de la entrada es exponencial en la longitud de entrada, por lo que un algoritmo de tiempo pseudopolinomial no necesariamente se ejecuta en tiempo polinomial con respecto a la longitud de entrada.

Un problema NP-completo con algoritmos de tiempo pseudo-polinomial conocidos se denomina débilmente NP-completo . Un problema NP-completo se denomina fuertemente NP-completo si se demuestra que no puede resolverse mediante un algoritmo de tiempo pseudo-polinomial a menos que P = NP . Los tipos fuerte/débil de NP-dureza se definen de forma análoga.

Ejemplos

Prueba de primalidad

Consideremos el problema de comprobar si un número n es primo , comprobando ingenuamente si ningún número en es divisible de manera exacta. Este enfoque puede requerir hasta divisiones, que es sublineal en el valor de n pero exponencial en la longitud de n (que es aproximadamente ). Por ejemplo, un número n ligeramente menor que 10.000.000.000 requeriría hasta aproximadamente 100.000 divisiones, aunque la longitud de n sea de solo 11 dígitos. Además, uno puede escribir fácilmente una entrada (por ejemplo, un número de 300 dígitos) para la cual este algoritmo es poco práctico. Dado que la complejidad computacional mide la dificultad con respecto a la longitud de la entrada (codificada), este algoritmo ingenuo es en realidad exponencial. Sin embargo, es tiempo pseudopolinomial. ${\displaystyle \{2,3,\dots ,{\sqrt {n}}\}}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}-1}$ ${\displaystyle \log(n)}$

Comparemos este algoritmo con un verdadero algoritmo numérico polinómico, por ejemplo, el sencillo algoritmo de la suma: sumar dos números de 9 dígitos requiere alrededor de 9 pasos simples y, en general, el algoritmo es verdaderamente lineal en la longitud de la entrada. Comparado con los números reales que se suman (en miles de millones), el algoritmo podría llamarse "tiempo pseudologarítmico", aunque ese término no es estándar. Por lo tanto, sumar números de 300 dígitos no es impráctico. De manera similar, la división larga es cuadrática: un número de m dígitos se puede dividir por un número de n dígitos en pasos (ver la notación Big O ). ${\displaystyle O(mn)}$

En el caso de la primalidad, resulta que hay un algoritmo diferente para probar si n es primo (descubierto en 2002) que se ejecuta en el tiempo . ${\displaystyle O((\log {n})^{6})}$

Problema de la mochila

En el problema de la mochila , se nos dan elementos con peso y valor , junto con una capacidad máxima de peso de una mochila . El objetivo es resolver el siguiente problema de optimización; informalmente, ¿cuál es la mejor manera de colocar los elementos en la mochila para maximizar el valor? ${\displaystyle n}$ ${\displaystyle w_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle W}$

maximizar ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

sujeto a y . ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$ ${\displaystyle x_{i}\in \{0,1\}}$

La solución de este problema es NP-hard , por lo que un algoritmo de tiempo polinomial es imposible a menos que P = NP . Sin embargo, es posible un algoritmo de tiempo utilizando programación dinámica ; dado que el número solo necesita bits para describirlo, este algoritmo se ejecuta en tiempo pseudopolinomial. ${\displaystyle O(nW)}$ ${\displaystyle W}$ ${\displaystyle \log W}$

Generalización a problemas no numéricos

Aunque la noción de tiempo pseudo-polinomial se utiliza casi exclusivamente para problemas numéricos, el concepto se puede generalizar: La función m es pseudo-polinomial si m ( n ) no es mayor que una función polinomial del tamaño del problema n y una propiedad adicional de la entrada, k ( n ). (Presumiblemente, k se elige para que sea algo relevante para el problema.) ^{[ ejemplos necesarios ]} Esto hace que los problemas polinomiales numéricos sean un caso especial al tomar k como el valor numérico de la entrada.

La distinción entre el valor de un número y su longitud es de codificación: si las entradas numéricas siempre se codifican en unario , entonces el pseudopolinomio coincidiría con el polinomio .

NP-dureza fuerte y débil frente a algoritmos de tiempo polinomial fuertes y débiles

Suponiendo que P ≠ NP, lo siguiente es cierto para problemas computacionales con números enteros: ^[2]

• Si un problema es débilmente NP-duro , entonces no tiene un algoritmo de tiempo débilmente polinomial (polinomial en el número de enteros y el número de bits en el entero más grande), pero puede tener un algoritmo de tiempo pseudopolinomial (polinomial en el número de enteros y la magnitud del entero más grande). Un ejemplo es el problema de la partición . Tanto la dureza débil NP como el tiempo polinomial débil corresponden a la codificación de los agentes de entrada en codificación binaria .

• Si un problema es fuertemente NP-hard , entonces ni siquiera tiene un algoritmo de tiempo pseudo-polinomial. Tampoco tiene un esquema de aproximación de tiempo completamente polinomial . Un ejemplo es el problema de 3 particiones . Tanto la fuerte NP-hardness como el tiempo pseudo-polinomial corresponden a la codificación de los agentes de entrada en codificación unaria .

Véase también

• Fuertemente NP-completo
• Tiempo cuasi-polinomial

Referencias

1. Michael R. Garey y David S. Johnson . Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . WH Freeman and Company, 1979.
2. Demaine, Erik. "Límites inferiores algorítmicos: diversión con pruebas de dureza, lección 2".