jueves, 14 de julio de 2011

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)

1 comentario:

  1. Por un lado es importante notar que no son todos de ninguna manera. Por otro lado, falta la referencia. +1

    ResponderEliminar