4.2: Una introducción a la teoría de la complejidad

Discusión 4.3.

Bob dice que realmente le están gustando estas cosas de matemáticas combinatorias. El carácter concreto del tema es atractivo. Pero no está seguro de que entienda el componente algorítmico. A veces ve cómo uno podría realmente calcular la respuesta a un problema, siempre que tuviera acceso a una computadora poderosa. En otras ocasiones, parece que un enfoque computacional podría estar fuera de su alcance, incluso con las mejores y más rápidas computadoras del mundo a fácil acceso. Carlos dice que puede ser mucho peor que eso. Hay problemas fácilmente declarables que nadie sabe atacar aunque todo el poder computacional del mundo se utilice en concierto. Y no hay nada en el horizonte que vaya a cambiar eso. De hecho, construye computadoras más rápidas y solo cambias el umbral para lo que es computable. Todavía habrá problemas de fácil comprensión que quedarán sin resolver.

4.2.1 Tres preguntas

Consideramos tres problemas con un punto de partida común. Se le da un conjunto\(S\) de 10,000 enteros positivos distintos, cada uno como máximo 100,000, y luego se le hacen las siguientes preguntas.

1. ¿83,172 es uno de los números enteros del conjunto\(S\)?

2. ¿Hay tres enteros en\(S\) cuya suma es 143,297?

3. ¿Se\(S\) puede particionar el conjunto como\(S=A \cup B\) con\(A∩B= \emptyset \), de modo que\(\sum_{a \in A} a = \sum_{b \in B} b\).

El primero de los tres problemas suena fácil, y lo es. Simplemente considera los números en el conjunto uno por uno y prueba para ver si alguno de ellos es 83,172. Puedes parar si alguna vez encuentras este número e informar que la respuesta es sí. Si devuelves un no respuesta, entonces tendrás que haber leído todos los números de la lista. De cualquier manera, te detienes con una respuesta correcta a la pregunta habiendo hecho como máximo 10,000 pruebas, e incluso la netbook más modesta puede hacer esto en un abrir y cerrar de ojos. Y si la lista se expande a 1,000,000 enteros, todo como máximo mil millones, aún puedes hacerlo fácilmente. De manera más general, si te dan un conjunto\(S\) de\(n\) números y un número entero\(x\) con la pregunta “¿Es\(x\) miembro de\(S\)?” , puedes responder esta pregunta en\(n\) pasos, con cada paso una operación de probar un número\(S\) para ver si es exactamente igual a\(n\). Entonces el tiempo de ejecución de este algoritmo es proporcional a\(n\), con la constante dependiendo de la cantidad de tiempo que tarda una computadora en realizar la operación básica de preguntar si un entero en particular es igual al valor objetivo.

El segundo de los tres problemas es un poco más desafiante. Ahora parece que debemos considerar los subconjuntos de 3 elementos de un conjunto de tamaño 10,000. Hay\(C(10,000,3)\) tales conjuntos. Por un lado, probar tres números para ver si su suma es de 143,297 es muy fácil, pero hay montones y montones de conjuntos para probar. Tenga en cuenta que\(C(10,000,3)=166,616,670,000\), y no demasiadas computadoras manejarán tantas operaciones. Además, si la lista se amplía a un millón de números, entonces tenemos más de\(10^{17}\) triples que probar, y eso está fuera de la mesa con el hardware de hoy.

Sin embargo, podemos considerar el caso general. Se nos da un conjunto\(S\) de\(n\) enteros y un número\(x\). Entonces se nos pregunta si hay tres enteros en\(S\) cuya suma está\(x\). El algoritmo que hemos descrito tendría tiempo de ejecución proporcional a\(n^3\), donde la constante de proporcionalidad depende del tiempo que se tarda en probar un triple de números para ver si hay suma\(x\). Por supuesto, esto depende a su vez de cuán grandes\(S\) puedan ser los enteros\(x\) y los enteros en.

El tercero de los tres problemas es diferente. Primero, parece ser mucho más difícil. Hay pares\(2^{n−1}\) complementarios de subconjuntos de un conjunto de tamaños\(n\), y uno de ellos involucra el conjunto vacío y el conjunto completo. Pero eso deja\(2^{n−1}−1\) pares para probar. Cada una de estas pruebas no es tan dura. Una netbook puede informar fácilmente si dos subconjuntos tienen la misma suma, incluso cuando los dos conjuntos forman una partición de un conjunto de tamaño 10,000, pero hay aproximadamente\(10^{3000}\) particiones para probar y ninguna pieza de hardware en el planeta tocará esa asignación. Y si subimos a un conjunto de tamaño 1,000,000, entonces la potencia informática combinada de todas las máquinas de la tierra no conseguirá hacer el trabajo.

En esta configuración, tenemos un algoritmo, es decir, probar todas las particiones, pero es totalmente inviable para conjuntos de\(n\) elementos cuando\(n\) es grande ya que tiene tiempo de ejecución proporcional a\(2^n\).

4.2.2 Certificados

Cada uno de los tres problemas que nos hemos planteado es en forma de pregunta de “sí/no”. Una respuesta “sí” a cualquiera de los tres puede justificarse proporcionando un certificado que pueda verificarse de manera eficiente. Por ejemplo, si contestas la primera pregunta con un sí, entonces podrías proporcionar la información adicional que encontrarás 83,172 como el entero en la línea 584 en el archivo de entrada. Por supuesto, también podrías proporcionar el código fuente para el programa de computadora, y dejar que un árbitro ejecute todo el procedimiento.

De igual manera, si contestas la segunda pregunta con un sí, entonces podrías especificar los tres números y especificar en qué parte del archivo de entrada se encuentran. Un árbitro imparcial podría entonces verificar, si importaba, que la suma de los tres enteros era realmente de 143 mil 297 y que estaban ubicados en los lugares especificados en el archivo de entrada. Alternativamente, podría nuevamente proporcionar el código fuente que requeriría que el árbitro pruebe todos los triples y verifique que haya uno que funcione.

De igual manera, un sí para la tercera pregunta admite un certificado de tamaño modesto. Solo es necesario especificar los elementos del subconjunto\(A\). El árbitro, que está equipado con una computadora, puede (a) verificar para ver que todos los números en\(A\) pertenecen a\(S\); (b) formar una lista del subconjunto que\(B\) consiste en aquellos enteros en los\(S\) que no pertenecen\(A\); y (c) computar las sumas de los enteros en\(A\) y el enteros en\(B\) y verificar que las dos sumas son iguales. Pero en este caso, no proporcionarías código fuente para el algoritmo, ya que no aparece (al menos nada en nuestra discusión hasta ahora proporciona uno) que sea una estrategia razonable para decidir este problema cuando el tamaño del problema es grande.

Ahora consideremos la situación con una respuesta de “no”. Cuando la respuesta a la primera pregunta es no, el certificado puede volver a ser un programa informático que permitirá al árbitro considerar todos los elementos de\(S\) y estar satisfecho de que el número en cuestión no está presente. Una observación similar se mantiene para la segunda pregunta, es decir, el programa es el certificado.

Pero la situación con la tercera pregunta vuelve a ser muy diferente. Ahora no podemos decirle al árbitro “Comprobamos todas las posibilidades y ninguna funcionó”. Esto no podría ser posiblemente una afirmación verdadera. Y no tenemos ningún programa informático que pueda ser manejado por nosotros o por el árbitro. Lo mejor que podríamos decir es que intentamos encontrar una partición adecuada y no pudimos hacerlo. En consecuencia, no sabemos cuál es realmente la respuesta correcta a la pregunta.

4.2.3 Operaciones

Muchos de los algoritmos que desarrollamos en este libro, así como muchos de los programas informáticos que resultan de estos algoritmos implican pasos básicos que se denominan operaciones. El significado de la palabra operación se deja intencionalmente como una noción imprecisa. Una operación podría ser simplemente comparar dos enteros para ver si son iguales; podría estar actualizando el valor de una variable\(x\) y reemplazándolo por\(x^2−3x+7\); y podría estar comprobando si dos sumas establecidas son iguales. En la tercera instancia, normalmente limitaríamos el tamaño de los dos subconjuntos así como los números enteros en ellos. En consecuencia, queremos poder decir que hay alguna constante\(c\) para que una operación se pueda llevar a cabo a tiempo como máximo\(c\) en una computadora. Diferentes computadoras producen diferentes valores de\(c\), pero esa es una discrepancia que podemos ignorar con seguridad.

4.2.4 Tamaño de entrada

Los problemas vienen en varios tamaños. Los tres problemas que hemos discutido en este capítulo tienen el mismo tamaño de entrada. En términos generales, este tamaño es de 10,000 bloques, con cada bloque capaz de contener un número entero de tamaño como máximo 100,000. En este texto, diremos que el tamaño de entrada de este problema es\(n=10,000\), y en cierto sentido ignorando la cuestión del tamaño de los enteros en el conjunto. Hay limitaciones obvias a este enfoque. Se nos podría dar un conjunto\(S\) de tamaño 1 y un elemento candidato\(x\) y que se nos pregunte si\(x\) pertenece a\(S\). Ahora supongamos que\(x\) es una cadena de bits del tamaño de un disco compacto típico, es decir, unos 700 megabytes de longitud. El solo hecho de leer la entrada única\(S\) para ver si es exactamente\(x\) llevará algún tiempo.

En una línea similar, considere el problema de determinar si un archivo\(x\) se encuentra en algún lugar de la estructura de directorios bajo\(y\) en un sistema de archivos Unix. Si vas solo por nombre, entonces esto puede ser relativamente fácil. Pero, ¿y si quieres estar seguro de que\(x\) está presente una copia exacta de? Ahora es mucho más desafiante.