Clases de complejidad P y NP

Aclaraciones

Por ejemplo, si tienes un problema y alguien dice "La respuesta a tu problema es el conjunto de números 1, 2, 3, 4, 5", un ordenador puede ser capaz, rápidamente, de averiguar si la respuesta es correcta o incorrecta, pero puede tardar mucho tiempo en dar con "1, 2, 3, 4, 5" por sí mismo. Otro ejemplo es la búsqueda de números primos. Es fácil comprobar si un número es primo, pero es muy difícil encontrar esos números en primer lugar. Para algunas preguntas interesantes y prácticas de este tipo, carecemos de cualquier forma de encontrar una respuesta rápidamente, pero si se nos proporciona una respuesta, es posible comprobar -es decir, verificar- la respuesta rápidamente. De este modo, los problemas de PN pueden considerarse como acertijos: puede ser difícil encontrar la respuesta a un acertijo, pero una vez que se escucha la respuesta, ésta parece obvia. En esta comparación (analogía), la pregunta básica es: ¿son los acertijos realmente tan difíciles como creemos que son, o nos estamos perdiendo algo?

Dado que este tipo de cuestiones P versus NP son tan importantes en la práctica, muchos matemáticos, científicos y programadores informáticos quieren demostrar la proposición general de que todo problema de comprobación rápida también puede resolverse rápidamente. Esta cuestión es lo suficientemente importante como para que el Instituto Matemático Clay conceda 1.000.000 de dólares a quien consiga aportar una prueba o una explicación válida que la refute.

Profundizando un poco más, vemos que todos los problemas P son problemas NP: es fácil comprobar que una solución es correcta resolviendo el problema y comparando las dos soluciones. Sin embargo, la gente quiere saber lo contrario: ¿Existen otros problemas NP que no sean problemas P, o todos los problemas NP son sólo problemas P? Si los problemas NP no son realmente lo mismo que los problemas P (P ≠ NP), significaría que no pueden existir formas generales y rápidas de resolver esos problemas NP, por mucho que busquemos. Sin embargo, si todos los problemas NP son problemas P (P = NP), significaría que sí existen nuevos métodos muy rápidos para resolver problemas. Sólo que aún no los hemos encontrado.

Dado que los mejores esfuerzos de científicos y matemáticos no han encontrado todavía métodos generales y fáciles para resolver problemas NP, mucha gente cree que hay problemas NP distintos de los problemas P (es decir, que P ≠ NP es verdadero). La mayoría de los matemáticos también creen que esto es cierto, pero actualmente nadie lo ha demostrado mediante un análisis matemático riguroso. Si se puede demostrar que NP y P son lo mismo (P = NP es verdadero), tendría un enorme impacto en muchos aspectos de la vida cotidiana. Por esta razón, la cuestión de P frente a NP es un tema importante y ampliamente estudiado.

Ejemplo

Supongamos que alguien quiere construir dos torres, apilando rocas de diferente masa. Uno quiere asegurarse de que cada una de las torres tiene exactamente la misma masa. Eso significa que habrá que poner las rocas en dos montones que tengan la misma masa. Si uno adivina una división de las rocas que cree que funcionará, será fácil comprobar si está en lo cierto. (Para comprobar la respuesta, uno puede dividir las rocas en dos montones y luego utilizar una balanza para ver si tienen la misma masa). Dado que es fácil comprobar este problema, llamado "Partición" por los informáticos -más fácil que resolverlo directamente, como veremos-, no es un problema P. ^[]

¿Qué tan difícil es de resolver, en definitiva? Si uno empieza con sólo 100 rocas, hay 2^{100-1}-1 = 633.825.300.114.114.700.748.351.602.687, o unas 6,3 x 10^{29} formas posibles (combinaciones) de dividir estas rocas en dos montones. Si se pudiera comprobar una combinación única de rocas cada día, se necesitaría 1,3 x 10^{22} o 1.300.000.000.000.000 de años de esfuerzo. A modo de comparación, los físicos creen que el universo tiene unos 1,4 x 10^{10} años (450.000.000.000.000 o unos 4,5 x 10^{17} segundos, o sea, una trillonésima parte del tiempo que nos llevaría nuestro esfuerzo de apilar rocas. Eso significa que si se toma todo el tiempo que ha pasado desde el comienzo del universo, habría que comprobar más de dos billones (2.000.000.000.000) de formas diferentes de dividir las rocas cada segundo, para comprobar todas las formas diferentes.

Si se programara un ordenador potente, para probar todas estas formas de dividir las rocas, se podrían comprobar 1 , 000 , 000 {\displaystyle 1,000,000} combinaciones por segundo utilizando los sistemas actuales. Esto significa que aún se necesitarían 2 , 000 , 000 {\displaystyle 2,000,000} ordenadores muy potentes, trabajando desde el origen del universo, para probar todas las formas de dividir las rocas.

Sin embargo, puede ser posible encontrar un método para dividir las rocas en dos montones iguales sin comprobar todas las combinaciones. La pregunta "¿Es P igual a NP?" es una forma abreviada de preguntar si puede existir algún método así.

Por qué es importante

Hay muchos problemas importantes de NP que la gente no sabe cómo resolver de forma más rápida que probando todas las respuestas posibles. He aquí algunos ejemplos:

• Un vendedor ambulante quiere visitar 100 ciudades en coche, empezando y terminando su viaje en casa. Tiene un suministro limitado de gasolina, por lo que sólo puede conducir un total de 10.000 kilómetros. Quiere saber si puede visitar todas las ciudades sin quedarse sin gasolina.
• Una escuela ofrece 100 clases diferentes, y el profesor tiene que elegir una hora para el examen final de cada clase. Para evitar las trampas, todos los alumnos de una clase deben hacer el examen de esa clase a la misma hora. Si un alumno se presenta a más de una clase, todos esos exámenes deben ser a una hora diferente. El profesor quiere saber si puede programar todos los exámenes en el mismo día para que todos los alumnos puedan hacer el examen de cada una de sus clases.
• Un agricultor quiere llevar al mercado 100 sandías de diferentes masas. Tiene que empaquetar las sandías en cajas. Cada caja sólo puede contener 20 kilos sin romperse. La agricultora necesita saber si 10 cajas serán suficientes para llevar las 100 sandías al mercado. (Esto es trivial, si no hay más de una sandía que pese más de 2 kg entonces se pueden colocar 10 cualesquiera en cada una de las cajas, si no hay más de diez sandías que pesen más de 2 kg entonces se puede colocar una de cada una de ellas en cada caja, etc., hasta llegar a una solución rápida; la observación será la clave para cualquier solución rápida como ésta o el problema del conjunto de números).
• Una gran galería de arte tiene muchas salas, y cada pared está cubierta con muchos cuadros caros. El propietario de la galería quiere comprar cámaras para vigilar estos cuadros, por si un ladrón intenta robar alguno de ellos. Quiere saber si 100 cámaras serán suficientes para asegurarse de que cada cuadro pueda ser visto por al menos una cámara.
• El problema de la camarilla: La directora de un colegio tiene una lista de los alumnos que son amigos entre sí. Quiere encontrar un grupo del 10% de los alumnos que sean todos amigos entre sí.

Tiempo Exponencial

En el ejemplo anterior, vemos que con 100 {\displaystyle 100} rocas, hay 2 100 {displaystyle 2^{100}} formas de dividir el conjunto de rocas. Con n {\displaystyle n} rocas, hay 2 n {displaystyle 2^{n}} combinaciones. La función f ( n ) = 2 n {\displaystyle f(n)=2^{n}} es una función exponencial. Es importante para NP porque modela el peor número de cálculos que se necesitan para resolver un problema y, por lo tanto, la peor cantidad de tiempo requerido.

Y hasta ahora, para los problemas difíciles, las soluciones han requerido en el orden de 2 n {desde el estilo 2^{n}} cálculos. Para cualquier problema particular, la gente ha encontrado maneras de reducir el número de cálculos necesarios. Uno podría averiguar que una manera de hacer sólo el 1% del peor de los casos el número de computación y que ahorra una gran cantidad de computación, pero eso es todavía 0,01 × ( 2 n ) {\displaystyle 0,01\\\Nveces (2^{n})} computaciones. Y cada roca extra todavía duplica el número de cálculos necesarios para resolver el problema. Hay ideas que pueden producir métodos para hacer aún menos cálculos produciendo variaciones del modelo: por ejemplo, 2 n / n 3 {\displaystyle 2^{n}/n^{3}}. . Pero la función exponencial sigue dominando a medida que n {\displaystyle n} crece.

Consideremos el problema de la programación de los exámenes (descrito anteriormente). Pero supongamos, a continuación, que hay 15000 estudiantes. Hay un programa informático que toma los horarios de los 15000 estudiantes. Se ejecuta en una hora y produce un calendario de exámenes para que todos los estudiantes puedan hacerlos en una semana. Cumple muchas reglas (no hay exámenes seguidos, no hay más de 2 exámenes en un periodo de 28 horas, ...) para limitar el estrés de la semana de exámenes. El programa se ejecuta durante una hora en la pausa de mitad de trimestre y todo el mundo conoce su calendario de exámenes con tiempo suficiente para prepararse.

Al año siguiente, sin embargo, hay 10 estudiantes más. Si el mismo programa se ejecuta en el mismo ordenador, esa hora se convertirá en 2 10 {displaystyle 2^{10}} horas, porque cada estudiante adicional duplica los cálculos. ¡Eso son 6 {\displaystyle 6} semanas! Si hubiera 20 estudiantes más, entonces

2 20 {\displaystyle 2^{20}} horas = 1048576 {\displaystyle 1048576}horas ~ 43691 {\displaystyle 43691} días ~ 113 {\displaystyle 113} años

Por lo tanto, para 15000 {estilos de presentación 15000} estudiantes, se necesita una hora. Para 15020 {\displaystyle 15020} estudiantes, se necesitan 113 {\displaystyle 113} años.

Como puedes ver, las funciones exponenciales crecen muy rápido. La mayoría de los matemáticos creen que los problemas NP más difíciles requieren un tiempo exponencial para ser resueltos.

Problemas NP-completos

Los matemáticos pueden demostrar que hay algunos problemas NP que son NP-Completos. Un problema NP-Completo es al menos tan difícil de resolver como cualquier otro problema NP. Esto significa que si alguien encontrara un método para resolver rápidamente cualquier problema NP-Completo, podría utilizar ese mismo método para resolver rápidamente todos los problemas NP. Todos los problemas mencionados anteriormente son NP-Completos, así que si el vendedor encontrara un método para planificar su viaje rápidamente, podría decírselo a la profesora, y ésta podría utilizar ese mismo método para programar los exámenes. El agricultor podría utilizar el mismo método para determinar cuántas cajas necesita, y la mujer podría utilizar el mismo método para encontrar la forma de construir sus torres.

Como un método que resuelva rápidamente uno de estos problemas puede resolverlos todos, hay mucha gente que quiere encontrar uno. Sin embargo, como hay tantos problemas NP-Completos diferentes y nadie hasta ahora ha encontrado una forma de resolver rápidamente ni siquiera uno de ellos, la mayoría de los expertos creen que resolver rápidamente los problemas NP-Completos no es posible.

Propiedades básicas

En la teoría de la complejidad computacional, la clase de complejidad NP-completa (abreviada NP-C o NPC), es una clase de problemas que tiene dos propiedades:

• Está en el conjunto de problemas NP (tiempo polinómico no determinista): Cualquier solución dada al problema puede ser verificada rápidamente (en tiempo polinomial).
• También está en el conjunto de problemas NP-duros: Aquellos que son al menos tan difíciles como los problemas más difíciles de NP. Los problemas que son NP-duros no tienen por qué ser elementos de NP; de hecho, pueden incluso no ser decidibles.

Resumen formal

NP-completo es un subconjunto de NP, el conjunto de todos los problemas de decisión cuyas soluciones pueden verificarse en tiempo polinómico; NP puede definirse de forma equivalente como el conjunto de problemas de decisión resueltos en tiempo polinómico en una máquina. Un problema p en NP está también en NP si y sólo si cualquier otro problema en NP se transforma en p en tiempo polinómico. NP-completo debía utilizarse como adjetivo: los problemas de la clase NP-completo eran como problemas NP+completos.

Los problemas NP-completos se estudian porque la capacidad de verificar rápidamente las soluciones de un problema (NP) parece correlacionarse con la capacidad de resolver rápidamente el problema (P). Se ha descubierto que todos los problemas en NP se resuelven rápidamente, lo que se denomina el conjunto de problemas P = NP. El único problema en NP-completo se resuelve rápidamente, más rápido que cada problema en NP también se resuelve rápidamente, porque la definición de un problema NP-completo establece que cada problema en NP debe ser rápidamente reducible a cada problema en NP-completo (se reduce en tiempo polinomial). [1]

Ejemplos

Se sabe que el problema de la satisfabilidad booleana es NP completo. En 1972, Richard Karp formuló 21 problemas que se sabe que son NP-completos. Se conocen como los 21 problemas NP-completos de Karp. Incluyen problemas como el problema de la programación entera, que aplica técnicas de programación lineal a los números enteros, el problema de la mochila, o el problema de la cubierta de vértices.