Complejidad computacional

Conceptos de informática

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Clases de complejidad

Clases de complejidad

Una animación que muestra todo el espacio de complejidad

Una imagen que muestra el espacio de problemas P

Clase de complejidad -->	P (Tiempo polinómico)
Qué significa	Se resuelven rápido y eficientemente
Ejemplo	Ordenar una lista
Analogía	"Archivar documentos alfabéticamente"
Clave	Son "fáciles" en términos computacionales

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Una imagen que muestra los espacios de problemas P y NP

Clase de complejidad -->	NP (Tiempo polinómico no determinista)
Qué significa	Solución verificable; encontrar una nueva es difícil
Ejemplo	Verificar que un Sudoku es correcto
Analogía	"Buscar un documento con datos incompletos"
Clave	Verificar es "fácil"; encontrar nuevas soluciones es difícil

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Una imagen que muestra los espacios de problemas P, NP y NP-Complete

Clase de complejidad -->	NP-Complete
Qué significa	Las más difíciles de NP. Especiales porque resuelven todo NP
Ejemplo	Problema del viajante
Analogía	"Rompecabezas complejo: fácil de verificar, difícil de resolver"
Clave	No hay solución eficiente conocida; si aparece, resolvería todo NP

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Una imagen que muestra P, NP, NP-Complete y NP-Hard

Clase de complejidad -->	NP-Hard
Qué significa	Tan difíciles como NP-Complete o más
Ejemplo	Planificación óptima con dependencias complejas y no verificable
Analogía	"Fijar la mejor hora con muchas restricciones y sin verificación rápida"
Clave	Puede ser impracticable de resolver

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Un diagrama que plantea la gran pregunta de investigación: ¿P=NP?

Conceptos de informática