Lista de Problemas NP-Completos

SAT (Problema de satisfacibilidad booleana, para fórmulas en forma normal conjuntiva)

• 0-1 INTEGER PROGRAMMING (Problema de la Programación lineal entera)
• CLIQUE (Problema del clique, véase también Problema del conjunto independiente)
  • SET PACKING (Problema del empaquetamiento de conjuntos)
  • VERTEX COVER (Problema de la cobertura de vértices)
    • SET COVERING (Problema del conjunto de cobertura)
    • FEEDBACK NODE SET
    • FEEDBACK ARC SET
    • DIRECTED HAMILTONIAN CIRCUIT (Problema del circuito hamiltoniano dirigido)
      • UNDIRECTED HAMILTONIAN CIRCUIT (Problema del circuito hamiltoniano no dirigido)
• 3-SAT (Problema de satisfacibilidad booleana de 3 variables por cláusula)
  • CHROMATIC NUMBER (Problema de la coloración de grafos)
    • CLIQUE COVER (Problema de la cobertura de cliques)
    • EXACT COVER (Problema de la cobertura exacta)
      • HITTING SET
      • STEINER TREE
      • 3-DIMENSIONAL MATCHING (Problema del matching tridimensional)
      • KNAPSACK (Problema de la mochila)
        • JOB SEQUENCING (Problema de las secuencias de trabajo)
        • PARTITION (Problema de la partición)
          • MAX-CUT (Problema del corte máximo)