Skip to content

Clase 2 — Complejidad Computacional: Problemas P, NP y Notación Big O

Resumen Ejecutivo

Esta sesión aborda la complejidad computacional como herramienta para clasificar problemas según su dificultad. Se introducen las clases de problemas P (resolubles en tiempo polinomial) y NP (verificables en tiempo polinomial), la famosa cuestión abierta P vs NP, y la notación Big O para expresar la eficiencia de algoritmos. También se diferencia entre algoritmo, problema e instancia, y se discuten aspectos prácticos de la eficiencia algorítmica (complejidad temporal vs. espacial, memoria estática vs. dinámica, método de Horner).

Conceptos Clave

  • Problema P: Problema cuya solución se puede encontrar en tiempo polinomial. ⚠️ EXAMEN
  • Problema NP: Problema cuya solución se puede verificar en tiempo polinomial (NO significa "no polinomial"). ⚠️ EXAMEN
  • P ⊆ NP: Todo problema P es también NP (si puedes resolverlo, puedes verificarlo), pero no se sabe si NP ⊆ P. ⚠️ EXAMEN
  • NP-Completo: Subclase de problemas NP especialmente difíciles; son verificables pero requieren mucho tiempo para resolverse. ⚠️ EXAMEN
  • NP-Hard (NP-Duro): Problemas al menos tan difíciles como los NP-completos; pueden ser o no verificables en tiempo polinomial. ⚠️ EXAMEN
  • Notación Big O: Notación asintótica que describe el crecimiento del tiempo de ejecución en función del tamaño de la entrada, quedándose solo con el término dominante. ⚠️ EXAMEN
  • Complejidad temporal: Número de operaciones que realiza un algoritmo en función del tamaño de entrada.
  • Complejidad espacial: Cantidad de memoria que consume un algoritmo.
  • Algoritmo determinista: Siempre produce la misma solución correcta con los mismos pasos; asociado a problemas P. ⚠️ EXAMEN
  • Algoritmo no determinista: Puede llegar a soluciones distintas según el punto de inicio; asociado a problemas NP. ⚠️ EXAMEN
  • Algoritmo / Problema / Instancia: Tres conceptos distintos que no deben confundirse. ⚠️ EXAMEN

Desarrollo del Temario

1. Diferencia entre Algoritmo, Problema e Instancia

Es fundamental distinguir tres conceptos que a menudo se confunden:

  • Algoritmo: La "receta", el paso a paso de cómo se resuelve un problema. Es la herramienta. Puede haber varios algoritmos distintos para un mismo problema, unos más eficientes que otros.
  • Problema: La "plantilla" o formulación general. Por ejemplo: "ordenar una lista de números" o "encontrar la ruta más corta".
  • Instancia: Un caso concreto del problema con datos específicos. Si el problema es "ordenar una lista", la instancia es la lista concreta [5, 3, 8, 1].

Ejemplo: En un problema de transporte de punto A a punto B que cuesta 10 litros de gasolina, si el mes siguiente el coste sube a 20 litros por la guerra, es el mismo problema pero una instancia diferente porque cambiaron los parámetros.

La complejidad de un problema se mide por el mejor algoritmo conocido que lo resuelve hasta ese momento, pero eso no significa que no pueda aparecer uno mejor en el futuro.

2. Clasificación P y NP

Problemas P — Se pueden resolver en tiempo polinomial. Puede tardar mucho (incluso semanas), pero puedes calcular cuánto tardará. Son problemas deterministas: siempre producen la misma solución correcta. ⚠️ EXAMEN

Problemas NP — Se pueden verificar en tiempo polinomial. Si alguien te da una solución candidata, puedes comprobar rápidamente si es correcta o no. ⚠️ EXAMEN

Ejemplo: Si te piden encontrar 10 números (positivos y negativos) de una lista cuya suma sea cero, encontrarlos puede ser muy difícil. Pero si alguien te da 10 números, verificar que suman cero es trivial. Esa es la diferencia entre resolver (P) y verificar (NP).

Relación P ⊆ NP: Todo problema P está contenido en NP, porque si puedes encontrar la solución, también puedes verificarla. La gran pregunta (sin resolver) es: ¿NP ⊆ P? Es decir, ¿todo problema verificable en tiempo polinomial también es resoluble en tiempo polinomial? ⚠️ EXAMEN

3. El problema abierto P vs NP

Es uno de los Problemas del Milenio del Clay Mathematics Institute, con un premio de un millón de dólares para quien lo resuelva. Nadie ha podido demostrar si P = NP o P ≠ NP.

La dificultad radica en que si tomas un problema supuestamente "duro" y logras resolverlo en tiempo polinomial, alguien podría argumentar que en realidad no era tan duro, generándose un ciclo sin fin.

4. Notación Asintótica — Big O

La Big O es la forma estándar de expresar la complejidad de un algoritmo. Lo que hace es: ⚠️ EXAMEN

  1. Eliminar constantes y términos menores del polinomio de tiempo.
  2. Quedarse solo con el término dominante (el que más crece).
  3. Evaluar el comportamiento en el peor caso (cuando \(n \to \infty\)).

Tipos comunes de complejidad (de mejor a peor):

Notación Tipo Comportamiento
\(O(1)\) Constante Siempre tarda lo mismo
\(O(\log n)\) Logarítmica Crece muy lentamente al aumentar datos
\(O(n)\) Lineal Crece proporcionalmente a los datos
\(O(n^2)\) Cuadrática Crece con el cuadrado de los datos
\(O(2^n)\) Exponencial Crece explosivamente

Ejemplo: Si ordenar 100 números tarda 1 segundo y es lineal \(O(n)\), entonces 200 números tardarán ~2 segundos. Pero si fuera cuadrática \(O(n^2)\), 200 números tardarían ~4 segundos.

Lo importante no es cuánto tarda en absoluto, sino cómo crece el tiempo al aumentar el tamaño de la entrada. ⚠️ EXAMEN

5. Complejidad Temporal vs. Espacial

  • Temporal: Número de operaciones por segundo. Se reporta en segundos, pero siempre indicando la máquina utilizada (procesador, cores) para que la comparación sea válida.
  • Espacial: Memoria consumida. Cobra especial importancia con datos grandes.

Ejemplo: Al comparar algoritmos en artículos de investigación, hay que especificar en qué máquina se ejecutaron. Si tu servidor tarda 1 segundo y el de otro investigador tarda 10, parece claro. Pero si uno usa un supercomputador y otro un portátil, la comparación directa en segundos no es válida.

6. Eficiencia algorítmica: el Método de Horner

Para evaluar un polinomio como \(f(x) = 2x^3 - 6x^2 + 2x - 1\), el método directo requiere calcular cada potencia por separado: \(x \cdot x \cdot x\), luego \(x \cdot x\), etc., resultando en muchas operaciones (multiplicaciones + sumas).

El método de Horner reescribe el polinomio factorizando progresivamente:

\[f(x) = ((2x - 6)x + 2)x - 1\]

El procedimiento: 1. Tomar el coeficiente de mayor grado (2). 2. Multiplicar por \(x\) y sumar el siguiente coeficiente (-6). 3. Multiplicar por \(x\) y sumar el siguiente coeficiente (+2). 4. Multiplicar por \(x\) y sumar el último coeficiente (-1).

Esto reduce significativamente el número de operaciones (solo \(n\) multiplicaciones y \(n\) sumas para un polinomio de grado \(n\), frente a muchas más en el método directo). ⚠️ EXAMEN

Ejemplo: Para \(f(x) = 2x^3 - 6x^2 + 2x - 1\) evaluado en \(x = 3\): en vez de calcular \(2 \cdot 3 \cdot 3 \cdot 3\), luego \(6 \cdot 3 \cdot 3\), etc., Horner hace: \(((2 \cdot 3 - 6) \cdot 3 + 2) \cdot 3 - 1\), con menos operaciones.

Este mismo principio de reescribir operaciones para reducir cómputo se aplica en muchos contextos: multiplicación de matrices, descomposiciones (Cholesky), almacenamiento de matrices triangulares, etc.

7. Memoria Estática vs. Dinámica

Cuando se trabaja con problemas pequeños, la asignación de memoria estática funciona bien. Pero al escalar:

  • Un vector declarado para 5 elementos al que se le meten 10 puede sobreescribir memoria de otras variables, causando errores difíciles de detectar.
  • La solución es usar memoria dinámica: crear vectores cuyo tamaño se ajusta en tiempo de ejecución y liberar memoria cuando ya no se necesita.

8. NP-Completo y NP-Hard

  • NP-Completo: Subclase de NP; problemas difíciles pero cuya solución es verificable en tiempo polinomial. ⚠️ EXAMEN
  • NP-Hard: Problemas al menos tan difíciles como los NP-completos. Pueden ser verificables o no en tiempo polinomial. ⚠️ EXAMEN
  • Los NP-completos son una subclase de los NP-hard.
  • El problema del viajante (TSP) es NP y también NP-hard. ⚠️ EXAMEN

9. Determinismo y No Determinismo

  • Determinista: Un algoritmo que, dado el mismo input, siempre sigue los mismos pasos y llega a la misma solución. Los problemas P son deterministas.
  • No determinista: Puede llegar a soluciones distintas según el punto de inicio. Los algoritmos bioinspirados suelen ser no deterministas: se ejecutan varias veces desde distintos puntos de inicio para comprobar si convergen a la misma solución. ⚠️ EXAMEN

Ejemplo: En optimización, se crean diferentes puntos de inicio aleatorios para ver si el algoritmo converge siempre al mismo punto (indicando que probablemente sea el óptimo global) o a puntos diferentes (indicando óptimos locales).

Preguntas de Autoevaluación

  1. ¿Cuál es la diferencia fundamental entre un problema de clase P y uno de clase NP?
  2. ¿Por qué se dice que P ⊆ NP? ¿Es cierto que NP ⊆ P?
  3. Explica la diferencia entre algoritmo, problema e instancia con un ejemplo propio.
  4. ¿Qué mide la notación Big O y por qué se eliminan las constantes y términos menores?
  5. ¿Qué ventaja ofrece el método de Horner frente a la evaluación directa de un polinomio?
  6. ¿Por qué la complejidad de un algoritmo no se mide en tiempo absoluto (segundos) sino en función del tamaño de la entrada?
  7. ¿Cuál es la relación entre problemas NP-completos y NP-hard? ¿Dónde se sitúa el problema del viajante?
  8. ¿Qué diferencia hay entre un algoritmo determinista y uno no determinista? ¿Cómo se relacionan con P y NP?
  9. ¿Por qué es importante especificar las características del hardware al reportar tiempos de ejecución en artículos científicos?
  10. ¿Qué problemas puede causar la memoria estática cuando se trabaja con instancias grandes y cómo se solucionan?

Guía generada automáticamente a partir de transcripción con faster-whisper + Claude Sonnet.