Teoría de la complejidad computacional para niños

La teoría de la complejidad computacional es una parte de la teoría de la computación que se encarga de clasificar los problemas computacionales según lo difíciles que son de resolver. También estudia cómo se relacionan estas clases de dificultad.

Un problema se considera "difícil por naturaleza" si para resolverlo se necesita una gran cantidad de recursos de una computadora, como tiempo o memoria, sin importar el método o programa que se use. La teoría de la complejidad computacional nos ayuda a entender esto de forma matemática, usando modelos de computación para medir cuánto tiempo y memoria se necesitan.

Uno de los objetivos principales de esta teoría es saber qué se puede hacer y qué no se puede hacer de forma práctica con una computadora. Es diferente del análisis de algoritmos, que se enfoca en cuánto recurso necesita un programa específico. La teoría de la complejidad computacional, en cambio, mira todos los programas posibles para resolver un problema.

Esta teoría clasifica los problemas que se pueden resolver con una cantidad limitada de recursos. Esto la diferencia de la teoría de la computabilidad, que solo se pregunta si un problema se puede resolver con un programa, sin importar cuánto tiempo o memoria tome.

Historia de la Complejidad Computacional

Antes de que se estudiara la dificultad de los programas, se sentaron las bases de esta teoría. Un paso muy importante fue la creación de las máquinas de Turing en 1936. Estas máquinas son un modelo teórico de cómo funciona una computadora, y demostraron ser muy útiles para entender la computación.

Sin embargo, pronto se dieron cuenta de que el modelo básico de la máquina de Turing no medía bien el tiempo y la memoria que una computadora necesitaba. Esta idea de medir el tiempo y el espacio según el tamaño de la información de entrada surgió a principios de los años 60, gracias a investigadores como Hartmanis y Stearns. Así nació la teoría de la complejidad computacional.

Al principio, los investigadores querían entender cómo se relacionaban estas nuevas formas de medir la dificultad. En 1965, Edmonds propuso que un buen programa era aquel que terminaba en un tiempo razonable, que se podía expresar con un polinomio. Esto llevó a una de las ideas más importantes de la teoría: la NP-completitud y la pregunta fundamental de si P es igual a NP.

El campo creció mucho cuando Stephen Cook y Leonid Levin demostraron, por separado, que existían problemas importantes que eran NP-completos. En 1972, Richard Karp fue más allá y mostró que 21 problemas de combinatoria y teoría de grafos, que eran muy difíciles de resolver, también eran NP-completos. En los años 70, surgieron más clases de dificultad a medida que se entendían mejor los diferentes modelos de computación.

En los años 80, se exploraron nuevos enfoques para problemas como P=NP. Aunque estos modelos tenían sus límites, ayudaron a entender mejor las fronteras de lo que se puede calcular.

En los años 90, se empezaron a estudiar nuevos modelos de computación, como las computadoras cuánticas. En estas, una misma tarea puede tener una dificultad diferente que en las computadoras clásicas. Sin embargo, construir estas computadoras y realizar cálculos complejos con ellas sigue siendo un gran desafío.

Problemas, Algoritmos y Dificultad

Para entender qué significa que un problema sea "difícil" o que varios problemas tengan una dificultad "equivalente", necesitamos conocer algunos términos básicos.

¿Qué es un Problema Computacional?

Un problema computacional es una pregunta que necesita una respuesta. Generalmente, tiene varios datos de entrada que pueden cambiar. Un problema se describe así:

1. Una descripción de todos los datos que se le pueden dar (entrada) y los que debe producir (salida).
2. Una frase que explica qué características debe tener la respuesta o solución.

Una "instancia" de un problema es cuando le damos valores específicos a todos los datos de entrada. Por ejemplo, en el problema de saber si un número es primo, una instancia sería el número 15. La solución sería "no", porque 15 no es primo. La instancia es la entrada, y la solución es la salida correspondiente.

Problemas de Decisión

Un problema de decisión es un tipo especial de problema computacional cuya respuesta es siempre "sí" o "no".

Podemos ver un problema de decisión como un conjunto de "palabras" (las instancias). Las palabras que pertenecen al conjunto son las que tienen respuesta "sí", y las que no, tienen respuesta "no". El objetivo es usar un programa para decidir si una entrada específica pertenece a ese conjunto. Si el programa dice "sí", se dice que "acepta" la entrada; si dice "no", la "rechaza".

Los problemas de decisión son muy importantes en la teoría de la complejidad computacional. Esto se debe a que la NP-completitud se aplica directamente a ellos, y casi cualquier problema puede transformarse en un problema de decisión.

¿Qué son los Algoritmos?

Los algoritmos son como recetas o instrucciones paso a paso para resolver problemas. Puedes imaginarlos como programas de computadora sencillos, escritos en un lenguaje especial.

Decimos que un algoritmo resuelve un problema si puede aplicarse a cualquier ejemplo de ese problema y siempre produce una solución correcta. Generalmente, buscamos el algoritmo más "eficiente" para un problema. La eficiencia se refiere a todos los recursos que el algoritmo necesita para funcionar.

Cuando hablamos del algoritmo "más eficiente", casi siempre nos referimos al más rápido. El tiempo que tarda un algoritmo es muy importante para saber si es útil en la práctica, por eso nos enfocamos mucho en este recurso.

Algoritmos de Tiempo Polinomial y Problemas Intratables

Los científicos de la computación distinguen entre algoritmos de Tiempo polinómico y algoritmos de tiempo exponencial. Los primeros se consideran "suficientemente eficientes" y los segundos, "muy ineficientes".

Un algoritmo de tiempo polinomial es aquel cuyo tiempo de ejecución crece de forma razonable a medida que el tamaño de la entrada aumenta. Por ejemplo, si la entrada es de tamaño n, el tiempo podría ser proporcional a n al cuadrado o n al cubo. Los algoritmos de tiempo exponencial, en cambio, crecen muchísimo más rápido. Si la entrada es n, el tiempo podría ser proporcional a 2 elevado a n. Esto significa que, para entradas un poco más grandes, el tiempo necesario se vuelve inmanejable.

La mayoría de los algoritmos de tiempo exponencial son como buscar todas las posibilidades, mientras que los de tiempo polinomial suelen ser el resultado de entender mejor la estructura del problema. En la teoría de la complejidad computacional, se considera que un problema no está "bien resuelto" hasta que se encuentra un algoritmo de tiempo polinomial para él. Por eso, llamamos a un problema intratable si es tan difícil que no existe un algoritmo de tiempo polinomial que lo resuelva.

Clases de Complejidad

Una clase de complejidad es un grupo de problemas que tienen la misma dificultad computacional.

¿Cómo se Definen las Clases de Complejidad?

Las clases de complejidad más simples se definen considerando:

• El tipo de problema: Aunque los problemas de decisión son los más comunes, las clases de complejidad pueden definirse para otros tipos de problemas.
• El modelo de computación: El modelo más usado es la Máquina de Turing determinista, pero también se usan máquinas de Turing no deterministas o cuánticas.
• El recurso que se limita y cuánto se limita: Por ejemplo, "tiempo polinomial" o "espacio logarítmico".

Máquinas de Turing Deterministas y la Clase P

La clase P incluye todos los problemas que pueden ser resueltos en tiempo polinomial por una máquina de Turing determinista. Una máquina de Turing determinista es como una computadora que sigue un solo camino de cálculo.

La clase P es muy importante porque:

1. Es estable: No importa qué modelo de computadora usemos (siempre que sea similar a la Máquina de Turing), los problemas en P seguirán siendo problemas en P.
2. En general, P representa los problemas que podemos resolver de forma realista con las computadoras actuales.

Computación No Determinista y la Clase NP

A menudo, podemos evitar probar todas las opciones para resolver problemas rápidamente. Sin embargo, para algunos problemas, no se conocen programas que los resuelvan en tiempo polinomial. Quizás existan, pero aún no los hemos descubierto, o quizás estos problemas son "inherentemente difíciles" y no pueden resolverse tan rápido.

La clase de complejidad NP agrupa los problemas que son "verificables" en tiempo polinomial. Esto significa que, si alguien te da una posible solución a un problema, tú puedes verificar si esa solución es correcta en un tiempo polinomial. A los problemas de esta clase se les llama problemas NP.

El nombre NP viene de no determinista en tiempo polinomial. Esto se refiere a otra forma de definir esta clase, usando Máquinas de Turing no deterministas. De forma sencilla, una máquina no determinista puede "adivinar" una solución y luego verificarla.

Un algoritmo no determinista tiene dos pasos: 1. Primero, "adivina" una posible solución. 2. Luego, verifica si esa solución es correcta. Si lo es, el algoritmo dice "sí"; si no, dice "no" o sigue buscando.

Al igual que la clase P, la clase NP no cambia mucho si usamos diferentes modelos de computación no deterministas, siempre que sean equivalentes.

Clases de Complejidad Importantes

Muchas clases de complejidad se definen limitando el tiempo o el espacio que usa un algoritmo. Aquí hay algunas de las más conocidas para problemas de decisión:

La Pregunta P=NP

La relación entre las clases P y NP es muy importante para entender la NP-completitud. Intuitivamente, pensamos que P es un subconjunto de NP. Y es cierto: cualquier problema que se resuelve rápidamente (en tiempo polinomial) por un algoritmo determinista, también puede ser resuelto por un algoritmo no determinista en tiempo polinomial. Esto es porque un algoritmo determinista puede usarse en la parte de verificación de un algoritmo no determinista. Así, si un problema está en P, también está en NP.

La pregunta P=NP es una de las más importantes en las ciencias de la computación. Si se encontrara una respuesta, tendría grandes consecuencias. Si P fuera igual a NP, significaría que cualquier problema cuya solución se pueda verificar rápidamente, también se podría resolver rápidamente. La mayoría de los investigadores creen que estas clases no son iguales, porque se ha intentado mucho, sin éxito, encontrar algoritmos rápidos para varios problemas en NP. También han intentado demostrar que son diferentes, pero eso implicaría probar que no existe un algoritmo "eficiente" para reemplazar la búsqueda de todas las posibilidades.

NP-Completitud

Reducción Polinomial

Una reducción es una forma de transformar un problema en otro. Imagina que un problema Q se puede "reducir" a otro problema Q' si cualquier ejemplo de Q se puede convertir "fácilmente" en un ejemplo de Q', y la solución de Q' nos da la solución para Q.

Existen muchos tipos de reducciones. Una de las más usadas es la reducción en tiempo polinomial, lo que significa que el proceso de transformación del problema toma un tiempo razonable.

Problemas NP-Completos

Las reducciones en tiempo polinomial nos permiten demostrar formalmente que un problema es al menos tan difícil como otro. Son clave para definir y entender los problemas NP-completos.

La clase de los problemas NP-completos contiene los problemas más difíciles dentro de NP. Si el problema P=NP no se ha resuelto, el hecho de reducir un problema B a otro problema A, significa que no se conoce una solución rápida para A. Esto es porque si A tuviera una solución rápida, B también la tendría. De manera similar, como todos los problemas NP pueden reducirse a este grupo, si se encontrara un problema NP-completo que se pudiera resolver rápidamente, significaría que P=NP.

Importancia de la NP-Completitud

Quizás la razón más fuerte por la que los científicos creen que P es diferente de NP es la existencia de los problemas "NP-completos". Esta clase tiene una propiedad curiosa: si algún problema NP-completo se pudiera resolver rápidamente, entonces todos los problemas en NP tendrían una solución rápida, es decir, P=NP. A pesar de años de estudio, no se ha encontrado ningún algoritmo rápido para ningún problema NP-completo.

Desde el punto de vista teórico, un investigador que quiera demostrar que P es diferente de NP podría enfocarse en un problema NP-completo. Si algún problema en NP requiere mucho tiempo, entonces uno NP-completo también lo hará. Además, un investigador que quiera demostrar que P=NP, solo necesita encontrar un algoritmo rápido para un problema NP-completo.

Desde el punto de vista práctico, saber que un problema es NP-completo puede evitar que se pierda tiempo buscando un algoritmo rápido que probablemente no existe. Aunque no tengamos pruebas matemáticas definitivas de que un problema no se puede resolver rápidamente, si es NP-completo, es una fuerte señal de que es muy difícil.

Cómo Enfrentar Problemas NP

Si P no es igual a NP, entonces los problemas NP-completos son intratables, es decir, muy difíciles de resolver de forma rápida.

Muchos problemas importantes en la vida real son NP-completos. No podemos simplemente rendirnos porque no sabemos cómo encontrar la solución perfecta rápidamente. Aunque un problema sea NP-completo, hay esperanza. Existen tres estrategias principales para lidiar con un problema NP-completo:

• Si la cantidad de datos de entrada es pequeña, un algoritmo que tome mucho tiempo podría ser aceptable.
• Se pueden encontrar algunos casos especiales del problema que sí se puedan resolver rápidamente.
• Podemos usar algoritmos de aproximación para encontrar soluciones que sean lo suficientemente buenas, aunque no sean perfectas, en un tiempo razonable. En la práctica, obtener soluciones cercanas a la ideal es muy útil. Estos algoritmos a menudo usan heurísticas y metaheurísticas, que son métodos para encontrar soluciones buenas sin garantizar que sean las mejores.

Véase también

En inglés: Computational complexity theory Facts for Kids

• Reducción (complejidad)
• Teorema de Cook-Levin
• Lista de 21 problemas NP-completos de Karp
• Clases de complejidad P y NP
• Teorema de la jerarquía temporal
• Anexo:Clases de complejidad
• Complejidad de Kolmogórov