21 Problema de Karp NP-completo

La lista de Karp es una lista que consiste en la formulación y demostración de la completitud NP de 21 problemas, publicada por Richard Karp en 1972 en su obra Reducibilidad entre problemas combinatorios [1 ] . 

Lista de tareas

• Problema de satisfacibilidad de la fórmula booleana ( SAT ) 
  • Programación de enteros binarios ( ing.  1-0 programación de enteros )
  • Problema de camarilla _ _  _
    • Establecer problema de embalaje _ _ 
    • Problema de cobertura de vértices _ _ 
      • Establecer
      problema de cobertura _ _ 
    • El problema de un conjunto de vértices de corte de bucle ( ing.  Conjunto de vértices de retroalimentación )
    • Problema de conjunto de  arco de retroalimentación _
      • Problema de gráfico hamiltoniano dirigido _ _  _ _ _ 
      • Problema gráfico hamiltoniano no dirigido _ _  _ _ _ 
• Problema de satisfacibilidad para fórmulas booleanas con tres literales ( ing.  3-SAT )
  • Problema de coloreado de gráficas _ _ 
    • Problema de portada
    de camarilla _ _ 
  • Problema de portada exacta ( Portada exacta en inglés  )
    • Problema de cobertura de vértices en hipergrafías _ 
    • El problema del  árbol mínimo de Steiner
    • Problema de emparejamiento tridimensional ( ing.  emparejamiento tridimensional )
    • Problema con la mochila _ _  _
      • Horario teoría _ _  _
      • Problema de partición _ _  _
      • El corte máximo del gráfico ( ing.  Corte máximo )

Véase también

Lista de problemas NP-completos

Notas

1. ↑ "Reducibilidad entre problemas combinatorios" Archivado el 29 de junio de 2011 en Wayback Machine , R. Karp , 1972