Please enable JavaScript.
Coggle requires JavaScript to display documents.
Actividad 21 - Coggle Diagram
Actividad 21
Clasificación de Problemas Computacionales
Definición
Categorías que agrupan problemas según la dificultad para resolverlos o verificarlos
Clave para entender la eficiencia de los algoritmos
Problemas P
Definición
Problemas que pueden resolverse en tiempo polinomial
Es decir, existe un algoritmo eficiente que los resuelve
Ejemplos
Ordenamiento (Bubble Sort, Merge Sort)
Búsqueda binaria
Caminos más cortos (Dijkstra, Floyd)
Características
Se resuelven y verifican eficientemente
Problemas NP
Definición
Problemas cuya solución puede verificarse en tiempo polinomial
Pero no se conoce un algoritmo eficiente para resolverlos
Ejemplos
Sudoku (verificar es fácil, resolver es difícil)
Problema de la mochila (Knapsack)
Clique máximo
Características
Solución difícil de encontrar, pero fácil de verificar
Problemas NP-completos
Definición
Problemas más difíciles de la clase NP
Si se encuentra una solución eficiente para uno, se resuelven todos los NP
Ejemplos
Problema del viajante (TSP)
Satisfacibilidad booleana (SAT)
Coloreo de grafos
Características
Son NP y tan difíciles como cualquier otro NP
Todos los problemas NP pueden reducirse a uno NP-completo
Relación entre clases
P ⊆ NP
No se ha demostrado si P = NP o P ≠ NP
Problema abierto en ciencia de la computación
Ejemplo práctico
Problema del viajante (TSP)
Definición
Dado un conjunto de ciudades y distancias entre ellas
Encontrar el camino más corto que visita todas una vez y regresa al inicio
Características
Fácil de verificar (sumar distancias)
Difícil de resolver con muchos nodos (combinaciones explotan)
Tipo de problema
Es NP-completo
No se conoce algoritmo que lo resuelva eficientemente para todos los casos
Conclusión
Los problemas P, NP y NP-completo ayudan a clasificar la dificultad computacional
Resolver uno NP-completo eficientemente resolvería todos los NP
La pregunta P vs NP es uno de los mayores desafíos abiertos en computación