Se dice que un problema de decisión puede resolverse en tiempo polinómico (o “en P “, para abreviar), si hay un algoritmo y un polinomio q tal que, dada cualquier entrada de tamaño n , el algoritmo responde la pregunta (¡correctamente!) En no más de q ( n ) pasos. En otras palabras, el peor momento para que el algoritmo resuelva el problema para una entrada de tamaño n debe ser O ( n ^ k ) para algunos k .
Por ejemplo, el problema del gráfico euleriano está en P. El algoritmo de búsqueda exhaustivo tarda demasiado en limitar el número de pasos por un polinomio. Pero hay otra forma . Veamos solo el caso conectado. El teorema de Euler nos dice que un gráfico conectado tiene un ciclo de Euler si y solo si cada vértice tiene un grado par. Entonces, si se nos da una gráfica conectada con n vértices en forma de una matriz de adyacencia n x n , en una serie de pasos que es O ( n ^ 2) podríamos decidir si la gráfica es Euleriana o no. Y la función q ( n ^ 2) = n ^ 2 es un polinomio.
Para otro ejemplo, el problema de 2-colorabilidad está en P.
El concepto P es importante en la informática teórica, porque los polinomios crecen a un ritmo modesto, en contraste con funciones como f ( n ) = n ! o g ( n ) = 2 ^ n . (Consulte la Tabla 4.3.1 en Análisis de algoritmos). Un algoritmo de tiempo polinómico es factible de ejecutar en una computadora. Un algoritmo de tiempo exponencial no lo es (excepto para entradas trivialmente pequeñas). Se dice que los problemas que no están en P son intratables .
- Si desmantelo un cubo de Rubik y luego lo vuelvo a montar de todas las formas posibles, ¿cuántos cubos distintos de Rubik son posibles?
- Cómo solucionar problemas y resolver problemas de capa 1
- ¿Cómo ayuda una base sólida en matemáticas discretas en la programación de computadoras?
- ¿Podré enseñarme el currículo de la Academia Phillips Exeter?
- ¿Qué piensan los informáticos teóricos de la hipótesis del universo matemático de Max Tegmark?
El concepto NP , “solucionable en tiempo polinómico no determinista”, es más difícil de explicar. Se dice que hay un problema en NP si hay un algoritmo con las siguientes propiedades: Primero, si la respuesta es “sí”, entonces debe existir evidencia de certificación (de tamaño polinomialmente limitado) tal que el algoritmo, dada la entrada y la evidencia, puede verificar la respuesta afirmativa en un número de pasos polinómicamente acotado. En segundo lugar, si la respuesta es “no”, entonces, por supuesto, no debe existir evidencia de certificación que acepte el algoritmo. (El libro menciona NP solo de pasada).
Por ejemplo, el problema del gráfico hamiltoniano está en NP (la evidencia de certificación es el ciclo hamiltoniano); el problema de 4 colorabilidad está en NP (la evidencia de certificación es la coloración); El problema de la satisfacción en la lógica está en NP . Y en todos estos casos, el problema no está en P hasta donde sabemos .
Se cree ampliamente que P no es igual a NP , y en particular que los tres problemas mencionados en el párrafo anterior no están en P. Pero los esfuerzos para demostrar que P difiere de NP hasta ahora no han tenido éxito.
La pregunta P vs. NP sigue siendo el problema abierto más importante en la informática teórica. Hay un premio de un millón de dólares por resolverlo).
El interés en la pregunta no es simplemente curiosidad ociosa. Existen esquemas criptográficos que se basan en la creencia de que problemas como estos no pueden responderse en una cantidad de tiempo factible. Si, al contrario de lo esperado, P y NP son iguales, entonces estos esquemas criptográficos no son seguros. (Si encuentra una manera de resolver todos los problemas de NP en tiempo polinómico, a la NSA le gustaría conversar con usted).
