CADENA DE DUREZA:

         SAT (Satisfacibilidad)
                ↓
      reducción polinomial
                ↓
      3-SAT (3-Satisfacibilidad)
                ↓
  Vertex Cover (Cubierta de Vértices)
                ↓
 Independent Set (Conjunto Independiente)
                ↓
       Clique (Clique máximo)
                ↓
  Graph Coloring (Coloración de grafos)
                ↓
 Hamiltonian Cycle (Ciclo Hamiltoniano)
                ↓
      TSP (Traveling Salesman)
                ↓
           ... cientos más

Si SAT es difícil → TODOS son difíciles
Si ALGUNO es fácil → SAT es fácil → P = NP

"""
VERTEX COVER (Cubierta de Vértices):
Dado: Grafo G=(V,E) y entero k
Pregunta: ¿Existe subconjunto S ⊆ V con |S| ≤ k
          tal que toda arista e ∈ E tiene al menos
          un extremo en S?

Ejemplo:
    1 --- 2
    |     |
    3 --- 4

S = {2, 3} es vertex cover de tamaño 2
  - Arista 1-2: cubierta por 2 ✓
  - Arista 2-4: cubierta por 2 ✓
  - Arista 3-4: cubierta por 3 ✓
  - Arista 1-3: cubierta por 3 ✓

---

INDEPENDENT SET (Conjunto Independiente):
Dado: Grafo G=(V,E) y entero k
Pregunta: ¿Existe subconjunto I ⊆ V con |I| ≥ k
          tal que NO hay aristas entre vértices de I?

Ejemplo (mismo grafo):
    1 --- 2
    |     |
    3 --- 4

I = {1, 4} es independent set de tamaño 2
  - No hay arista entre 1 y 4 ✓
"""

def vertex_cover_to_independent_set(G, k):
    """
    Reducción de Vertex Cover a Independent Set
    
    Args:
        G: grafo
        k: tamaño máximo de vertex cover
    
    Returns:
        (G', k'): instancia equivalente de Independent Set
    """
    # El grafo es el mismo
    G_prime = G
    
    # El tamaño se complementa
    n = len(G.vertices)
    k_prime = n - k
    
    return G_prime, k_prime

def independent_set_to_vertex_cover(G, k):
"""
Reducción de Independent Set a Vertex Cover
(Dirección inversa)
"""
G_prime = G
n = len(G.vertices)
k_prime = n - k

    return G_prime, k_prime

# Ejemplo de uso

print("="*60)
print("REDUCCIÓN: VERTEX COVER ↔ INDEPENDENT SET")
print("="*60 + "\n")

# Grafo de ejemplo

class Graph:
def **init**(self, n):
self.vertices = list(range(1, n + 1))
self.edges = []

    def add_edge(self, u, v):
        self.edges.append((u, v))

    def __repr__(self):
        return f"Grafo: vértices={self.vertices}, aristas={self.edges}"

# Crear grafo

G = Graph(4)
G.add_edge(1, 2)
G.add_edge(2, 4)
G.add_edge(3, 4)
G.add_edge(1, 3)

print("Grafo original:")
print(G)
print()

print("Estructura:")
print(" 1 --- 2")
print(" | |")
print(" 3 --- 4")
print()

# Problema 1: Vertex Cover con k=2

k_vc = 2
print(f"VERTEX COVER: ¿Existe cubierta de tamaño ≤ {k_vc}?")

G_is, k_is = vertex_cover_to_independent_set(G, k_vc)

print(f"\nReducción a INDEPENDENT SET:")
print(f" Grafo: {G_is}")
print(f" k' = n - k = {len(G.vertices)} - {k_vc} = {k_is}")
print(f" Pregunta: ¿Existe independent set de tamaño ≥ {k_is}?")

print("\n" + "="*60)
print("SOLUCIONES:")
print("="*60)

print("\nVertex Cover de tamaño 2:")
print(" S = {2, 3}")
print(" Verifica:")
print(" Arista (1,2): 2 ∈ S ✓")
print(" Arista (2,4): 2 ∈ S ✓")
print(" Arista (3,4): 3 ∈ S ✓")
print(" Arista (1,3): 3 ∈ S ✓")

print("\nIndependent Set correspondiente:")
print(" I = V - S = {1, 4}")
print(" Tamaño: 2 = k'")
print(" Verifica:")
print(" No hay arista entre 1 y 4 ✓")

print("\n" + "="*60)
print("IMPLICACIÓN:")
print("="*60)
print("""
Si pudiéramos resolver Independent Set en tiempo polinomial:

1. Dada instancia de Vertex Cover (G, k)
2. Reducir a (G, n-k) en O(1)
3. Resolver Independent Set en tiempo poli
4. Retornar respuesta

Resultado: Vertex Cover también es polinomial

Por contraposición:

- Si Vertex Cover es difícil (NP-completo)
- Entonces Independent Set también es difícil
- Ambos son igualmente difíciles
  """)

HIPÓTESIS MAYORITARIA: P ≠ NP

┌─────────────────────────────────────────┐
│ NP                                      │
│ (Verificables en tiempo polinomial)     │
│                                         │
│   ┌──────────────────────────────────┐  │
│   │ NP-Completos                     │  │
│   │ (Los más difíciles de NP)        │  │
│   │                                  │  │
│   │ SAT, 3-SAT, Vertex Cover,       │  │
│   │ Independent Set, Clique,         │  │
│   │ Graph Coloring, TSP, ...         │  │
│   │                                  │  │
│   └──────────────────────────────────┘  │
│                                         │
│   ┌──────────────────┐                  │
│   │ P                │                  │
│   │ (Resolubles en   │                  │
│   │ tiempo poli)     │                  │
│   │                  │                  │
│   │ Sorting, MST,    │                  │
│   │ Shortest Path    │                  │
│   └──────────────────┘                  │
│                                         │
└─────────────────────────────────────────┘

SI P = NP (poco probable):
  Los dos círculos serían idénticos
  Todos los problemas NP serían resolubles en tiempo poli
  Revolución en ciencia de la computación

"""
PROBLEMAS NP-COMPLETOS CLÁSICOS

LÓGICA:
  • SAT (Satisfacibilidad booleana)
  • 3-SAT (SAT con cláusulas de 3 literales)
  • Circuit SAT

GRAFOS:
  • Vertex Cover (Cubierta de vértices)
  • Independent Set (Conjunto independiente)
  • Clique (Clique máximo)
  • Graph Coloring (Coloración de grafos)
  • Hamiltonian Cycle (Ciclo hamiltoniano)
  • Hamiltonian Path (Camino hamiltoniano)

OPTIMIZACIÓN:
  • TSP (Traveling Salesman - decisión)
  • Knapsack (Mochila 0/1 - decisión)
  • Bin Packing (Empaquetado)
  • Job Scheduling (Calendarización)

NUMÉRICOS:
  • Subset Sum (Suma de subconjuntos)
  • Partition (Partición)
  • 3-Partition

JUEGOS Y PUZZLES:
  • Sudoku (versión generalizada)
  • Minesweeper (Buscaminas - consistencia)
  • Tetris (optimizar altura)

CADENAS:
  • Longest Common Subsequence (k secuencias)
  • Shortest Superstring

¡Y CIENTOS MÁS!

Todos son equivalentes en dificultad.
Si uno cae (algoritmo poli), todos caen.
"""

def tsp_optimization(distances):
    """
    PROBLEMA DE OPTIMIZACIÓN (difícil probar NP-completitud):
    Encontrar el tour de costo mínimo
    """
    # Este es el problema "natural" pero difícil de trabajar
    # en teoría de complejidad
    pass

def tsp_decision(distances, k):
"""
PROBLEMA DE DECISIÓN (NP-completo):
¿Existe tour con costo ≤ k?

    Args:
        distances: matriz de distancias
        k: límite superior de costo

    Returns:
        True si existe tour con costo ≤ k
        False en caso contrario
    """
    # Si pudiéramos resolver esto en tiempo polinomial,
    # podríamos resolver la versión de optimización:
    #   - Buscar k binariamente entre 0 y suma_total
    #   - Cada verificación es polinomial
    #   - O(log(suma_total)) llamadas
    #   - Total: polinomial
    pass

print("="*60)
print("TSP: OPTIMIZACIÓN VS DECISIÓN")
print("="*60 + "\n")

print("OPTIMIZACIÓN (natural):")
print(" Entrada: Grafo con distancias")
print(" Pregunta: ¿Cuál es el tour más corto?")
print(" Salida: Secuencia de ciudades y costo")
print()

print("DECISIÓN (teoría):")
print(" Entrada: Grafo con distancias + entero k")
print(" Pregunta: ¿Existe tour con costo ≤ k?")
print(" Salida: SÍ o NO")
print()

print("EQUIVALENCIA:")
print(" Si DECISIÓN es difícil → OPTIMIZACIÓN es difícil")
print(" Si OPTIMIZACIÓN es fácil → DECISIÓN es fácil")
print()

print("¿POR QUÉ DECISIÓN?")
print(" ✓ Simplifica teoría matemática")
print(" ✓ Output booleano (SÍ/NO) más simple")
print(" ✓ Composición de reducciones más clara")
print(" ✓ Captura la esencia de la dificultad")

PLANTILLA DE DEMOSTRACIÓN:

Teorema: El problema X es NP-completo.

Demostración:

1. X ∈ NP:
   Dado un certificado (solución candidata) para X,
   podemos verificar en tiempo polinomial que:
      [describir verificación]
   Por tanto, X ∈ NP.

2. X es NP-Hard:
   Reducimos de [problema NP-completo conocido Y].

   Dada una instancia I_Y de Y:

   a) Construcción (tiempo polinomial):
      [describir cómo construir instancia I_X de X]

   b) Correctitud (→):
      Si I_Y tiene solución S_Y, entonces:
         [mostrar que I_X tiene solución S_X]

   c) Correctitud (←):
      Si I_X tiene solución S_X, entonces:
         [mostrar que I_Y tiene solución S_Y]

   La reducción toma tiempo polinomial porque:
      [análisis de complejidad]

   Por tanto, Y ≤_p X, y X es NP-Hard.

Conclusión: X es NP-completo.