Complejidad

Hoy daremos un paseo corto por la complejidad.
A diario nos topamos con problemas, algunos más sencillos que otros, pero ¿somos capaces de distinguir de antemano cuáles son aquellos problemas sencillos y cuáles los difíciles? Para hacer esto de una forma formal, es que se define la complejidad de un problema. La complejidad mide, básicamente, qué tanto trabajo es necesario para resolver un problema dado.
Para simplificar las cosas, tomemos en cuenta únicamente los llamados problemas de decisión: aquellos cuya respuesta es siempre sí o no. Por ejemplo, saber si un número n es primo, es un problema de decisión: todo número entero positivo es primo o no lo es. Así, dado un número cualquiera, somos capaces de contestar de forma certera si es primo o no.
Ahora, queremos saber qué tanto trabajo necesitamos para resolverlo. El trabajo lo podemos medir en el número de pasos que tenemos que dar para llegar a la solución. Pero ojo que ese número de pasos no depende únicamente del problema, sino también de la instancia que se está usando. En nuestro ejemplo de números primos, obviamente necesitamos menos pasos para verificar si el número 4 es primo, que para verificar si 3421354235 lo es. Por tanto, la medición del número de pasos se hace en base al tamaño de la instancia en turno.
Ahora, los estudios de complejidad se hacen para saber si es posible resolverlos en un tiempo razonable. Dado que las computadoras acutales son capaces de realizar miles de pasos por segundo, no nos importa realmente saber el número exacto de pasos. Lo que nos interesa es saber si es (o será) posible resolver un problema para entradas grandes dentro de un tiempo razonable.
Aquí es donde entran las definiciones de las clases de complejidad que nos encontramos comúnmente. Como ya dije, no nos interesa saber el número exacto de pasos, pero podemos saber, por ejemplo, si ese número de pasos está acotado por un polinomio. Si es así, sabemos que, al aumentar el tamaño de la instancia, el número de pasos que debemos realizar para resolver el problema no crece tanto. Por ejemplo, supongamos que queremos decidir si una cadena de texto contiene la letra "a". Para resolverlo, lo único que tenemos que hacer es leer toda la cadena hasta encontrar una "a" o llegar al final. Hacer esto, necesita básicamente tantos pasos como larga es la cadena. Si duplicamos la longitud de la cadena, necesitamos el doble de tiempo, lo que resulta razonable.
Si, en cambio, no hay ningún polinomio que acote el número de pasos, sabemos que el número de pasos crece exponencialmente al aumentar el tamaño de la entrada. Supongamos que sabemos que el problema requiere 2^n pasos para encontrar la solución, donde n es la longitud de la instancia en cuestión. Entonces, si aumento el tamaño de la instancia en 1, necesito el doble de tiempo para resolver el problema. Así, para entradas grandes, pero realistas, no tenemos esperanza de ser capaces de resolver ese problema dentro de nuestras vidas.
En otra entrada intentaré ir a más detalle en esto. Dejen en los comentario sus dudas, e intentaré resolverlas lo mejor posible.