Lista de 21 problemas NP-Completos. (Extra)

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)

(Espero que esto les ayude con su tarea)

Bibliografia:
http://es.wikipedia.org/wiki/Lista_de_21_problemas_NP-completos_de_Karp