P frente a NP

El problema P contra NP es uno de los problemas más importantes y no resueltos en la informática.

Complejidad Computacional

La complejidad computacional es una medida de la dificultad (en términos de tiempo, memoria, o algún otro criterio) de ejecutar un algoritmo.

Ejemplo: Ordenar una lista. Usando el algoritmo Quicksort, la complejidad es n2n^2n2 en el peor de los casos y nlog⁡(n)n \log(n)nlog(n) en promedio, donde nnn es el tamaño del arreglo de entrada.

Ejemplo: Encontrar un valor en una lista desordenada.

Promedio: (N+1)/2 comparaciones

Peor caso: N

El algoritmo de búsqueda lineal es un algoritmo O(n).

¿Qué es P vs NP?

La clase P consiste en problemas cuyas soluciones pueden ser ENCONTRADAS en tiempo polinómico.
La clase NP consiste en problemas cuyas soluciones pueden ser VERIFICADAS en tiempo polinómico.

En otras palabras, el tiempo polinómico puede ser O(N²), O(N⁷), o cualquier complejidad polinómica. La idea detrás de esta clasificación es que estos problemas se consideran "fáciles" en el sentido de que pueden ser resueltos con las capacidades computacionales actuales.

¿Cuál es la diferencia entre encontrar una solución y verificar una solución?

Ejemplo:

Para ENCONTRAR UNA SOLUCIÓN, necesitaríamos probar si 4819 es divisible por 2, 3, 5, 7, 11, 13, 17—es decir, verificar qué números primos lo dividen.

Sin embargo, el problema inverso es mucho más simple:

Con una calculadora básica, podemos VERIFICAR que 79 × 61 = 4819.

¡Toda la criptografía RSA moderna se basa en esta asimetría!

Un problema puede ser exponencialmente difícil de resolver, con complejidad O(2^N) o O(N!), pero aún ser fácil de verificar—lo que significa que pertenece a la clase NP.

Una máquina determinística se refiere a una máquina de Turing, un modelo abstracto de cómputo. Una máquina de Turing no determinista, por otro lado, se comporta como una máquina de Turing regular pero puede explorar un número infinito de ramas en paralelo.

En resumen:

• Clase P: Tiempo polinómico – ENCONTRAR la solución en tiempo polinómico (P).

• Clase NP: Tiempo Polinómico No Determinista – VERIFICAR la solución en tiempo polinómico (P).

(¡NP no significa "No Polinómico" – no cometas este error!)

NP-Completo y NP-Difícil

Claramente, P está contenido dentro de NP—ya que si es posible encontrar una solución, también es posible verificar si una solución satisface el problema.

Sin embargo, en el Zoológico de la Complejidad, hay algunas entidades más. ¿Cuáles son?

NP-Completo y NP-Difícil

• NP-Completo – Estos son los problemas de decisión más difíciles dentro de la clase NP.

Un problema es NP-Completo si cada problema en NP puede ser convertido en él en tiempo polinómico.

Ejemplos: Problema del Viajante, Satisfacibilidad (SAT), Cubierta de Vértices, etc.
Consulta Los 21 Problemas NP-Completos de Karp para más ejemplos.

En otras palabras, imagina que tenemos un solucionador eficiente (algoritmo en tiempo polinómico) para el Problema del Viajante. Dado que cada problema NP puede ser transformado en el Problema del Viajante, resolverlo eficientemente significaría que todos los problemas NP también podrían ser resueltos eficientemente. Si resuelves un problema NP-Completo, los resuelves todos.

• NP-Difícil – Estos son problemas que son al menos tan difíciles como NP-Completo, pero que no necesariamente tienen soluciones que pueden ser verificadas en tiempo polinómico.

Los problemas de optimización que surgen en la vida real, como la optimización de la cosecha o la planificación forestal, a menudo involucran variables lineales e enteras con numerosas restricciones—estos son típicamente NP-Difíciles.

¿Es P = NP o no?

La gran pregunta es si P = NP o no. Puede parecer simple, pero hasta el día de hoy, nadie ha podido probar o refutar esta afirmación.

Incluso hay un premio de 1 millón de dólares para quien resuelva la cuestión. Es uno de los siete Problemas del Milenio, promovido por el Instituto de Matemáticas Clay.

🔗 Problemas del Milenio – Instituto de Matemáticas Clay

El Instituto Clay fue inspirado por los 23 problemas propuestos por el matemático David Hilbert en 1900, que, de una forma u otra, guiaron el desarrollo de las matemáticas en las décadas siguientes.

Con respecto al Zoológico de la Complejidad, dado que resolver la pregunta principal (P vs NP) es difícil, los matemáticos se centran en resolver problemas que pueden ser abordados. Esto ha llevado a la creación de varias otras definiciones de tipos de complejidad computacional.

¿Resuelve la Computación Cuántica?

Cuando surgen nuevos paradigmas de cómputo, como la computación cuántica, entender su potencial ayuda a definir límites y expectativas.

En el caso de la computación cuántica, se cree que es más poderosa que la clase P, pero no capaz de resolver todos los problemas NP. También puede ser capaz de resolver problemas más allá de la clase NP.

De hecho, solo porque un problema es polinómico no significa necesariamente que sea fácil. Un problema con complejidad O(N⁹⁹⁹⁹) seguiría siendo extremadamente difícil de resolver.

Por otro lado, los problemas NP-completos con pequeños tamaños de entrada pueden ser resueltos con el poder computacional actual. En la práctica, los solucionadores modernos han hecho que problemas previamente intratables sean al menos mínimamente solucionables para aplicaciones del mundo real. Gracias a los avances en hardware y software, es posible manejar problemas NP-Difíciles, al menos una parte significativa de ellos.

Bueno, en todo caso, hay un premio de 1 millón de dólares para quien esté dispuesto a profundizar en el tema. ¡Solo no ganes y rechaces el premio como hizo Grigori Perelman (consulta el enlace a continuación)!

🔗 El Hombre Que Merecía un Premio de 1 Millón de Dólares—Y Lo Rechazó