En esta sección exploraremos los conceptos de complejidad NP, problemas NP-completos y NP-hard, y su impacto en la computación. También veremos ejemplos en Java, JavaScript, TypeScript y Python.

✅ Objetivo:

Entender la diferencia entre problemas P, NP, NP-completos y NP-hard.
Analizar la dificultad de ciertos problemas.
Implementar ejemplos de problemas NP en código.

📌 1. ¿Qué son P y NP?

Los problemas se clasifican en P y NP según la dificultad de su resolución:

Clase	Definición
P (Polynomial)	Se pueden resolver en tiempo polinómico (`O(n^k)`).
NP (Nondeterministic Polynomial)	Si encontramos una solución, podemos verificarla en tiempo polinómico.

📌 Ejemplo: Multiplicación vs. Factores Primos

Multiplicar dos números grandes (P) → Rápido (O(n^2)).
Encontrar los factores primos (NP) → Lento, pero fácil de verificar.

📌 2. Problemas NP-Completos y NP-Hard

Algunos problemas NP son más difíciles, y caen en una de estas dos categorías:

Clase	Definición
NP-Completo	Es un problema NP tan difícil que si encontramos una solución rápida, resolveríamos todos los problemas NP.
NP-Hard	Aún más difícil que NP-completo. Puede no estar en NP (no verificable en tiempo polinómico).

📌 Ejemplos:

Problema de la Mochila (Knapsack) → NP-Completo
Problema del Viajero (TSP) → NP-Completo
Problema de Halting → NP-Hard (No se puede verificar en O(n^k))

📌 3. Problema de la Mochila (Knapsack) (NP-Completo)

Dado un conjunto de objetos con peso y valor, y una mochila con capacidad W, debemos maximizar el valor sin exceder W.

📌 Ejemplo: Programación Dinámica (O(nW))

1// Java - O(nW) - Problema de la Mochila (DP)
2public class Knapsack {
3    public static int knapsack(int W, int[] weights, int[] values) {
4        int n = weights.length;
5        int[][] dp = new int[n + 1][W + 1];
6
7        for (int i = 1; i <= n; i++) {
8            for (int w = 0; w <= W; w++) {
9                if (weights[i - 1] <= w) {
10                    dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
11                } else {
12                    dp[i][w] = dp[i - 1][w];
13                }
14            }
15        }
16        return dp[n][W];
17    }
18}

✅ Complejidad:

O(nW), donde n es el número de objetos y W es la capacidad de la mochila.
Mucho mejor que O(2ⁿ), pero sigue siendo costoso.

📌 4. Problema del Viajero (TSP) (NP-Completo)

Dado un conjunto de ciudades y sus distancias, ¿cuál es la ruta más corta que visita todas las ciudades exactamente una vez y vuelve al inicio?

📌 Ejemplo: Fuerza Bruta (O(n!))

1// Java - O(n!) - Problema del Viajero con Backtracking
2import java.util.*;
3
4public class TSP {
5    private static int tsp(int[][] graph, boolean[] visited, int pos, int n, int count, int cost, int minCost) {
6        if (count == n && graph[pos][0] > 0) {
7            return Math.min(minCost, cost + graph[pos][0]);
8        }
9        for (int i = 0; i < n; i++) {
10            if (!visited[i] && graph[pos][i] > 0) {
11                visited[i] = true;
12                minCost = tsp(graph, visited, i, n, count + 1, cost + graph[pos][i], minCost);
13                visited[i] = false;
14            }
15        }
16        return minCost;
17    }
18
19    public static int solveTSP(int[][] graph) {
20        int n = graph.length;
21        boolean[] visited = new boolean[n];
22        visited[0] = true;
23        return tsp(graph, visited, 0, n, 1, 0, Integer.MAX_VALUE);
24    }
25}

✅ Complejidad:

O(n!) (Factorial) → Explosión combinatoria.
Aproximaciones (Greedy, Branch & Bound) son más eficientes.

📌 5. Problema de Satisfacción de Restricciones (3-SAT) (NP-Completo)

📌 Problema: Dado un conjunto de expresiones lógicas con 3 variables, ¿existe una asignación de true/false que las haga todas verdaderas?

📌 Ejemplo de Expresión: [ (A \lor B \lor ¬C) \land (¬A \lor C \lor D) \land (B \lor ¬D \lor ¬E) ]

Este problema es NP-Completo porque:

Verificar una solución es rápido (O(n)).
Encontrar una solución en fuerza bruta (O(2ⁿ)) es impráctico.

✅ Solución:

Algoritmos heurísticos (Backtracking, SAT solvers).

📌 6. Problema del Halting (NP-Hard)

📌 Problema:
Dado un programa y una entrada, ¿se detendrá o se ejecutará para siempre?

📌 Ejemplo de Código Problemático:

1// Java - Problema del Halting (Ejemplo)
2public class HaltingProblem {
3    public static void main(String[] args) {
4        while (true) {
5            System.out.println("Ejecutando...");
6        }
7    }
8}

✅ Conclusión:

No existe un algoritmo que pueda determinar si cualquier programa se detendrá.
Es NP-Hard porque ni siquiera podemos verificarlo en O(n^k).

📌 7. Comparación de Complejidades en Problemas NP

Problema	Clase	Complejidad
Multiplicación	P	`O(n^2)`
Búsqueda Binaria	P	`O(log n)`
Mochila 0/1	NP-Completo	`O(nW)` (DP)
Problema del Viajero (TSP)	NP-Completo	`O(n!)`
3-SAT (Satisfacción de Restricciones)	NP-Completo	`O(2ⁿ)`
Problema del Halting	NP-Hard	No resolvible

📌 Conclusión:

Si un problema es P, podemos resolverlo eficientemente.
Si un problema es NP-Completo, no hay una solución rápida conocida.
Si un problema es NP-Hard, ni siquiera podemos verificar la solución en O(n^k).