Vintiun problemes NP-complets de Karp

En teoria de complexitat computacional, els vintiun (21) problemes NP-complets de Karp són un conjunt de problemes computacionals famosos, que tracten sobre combinatòria i teoria de grafos i que complixen la característica en comuna de que tots ells pertanyen a la classe de complexitat dels NP-complets. La demostració va ser elaborada en 1972 pel informàtic teòric Richard Karp, en el seu treball seminal "Reducibility Among Combinatorial Problems" (Reducibilidad entre Problemes Combinatoris),^[1] com a aprofundiment del treball de Stephen Cook, qui en 1971 havia demostrat un dels resultats més importants i pioners de la complexitat computacional: la NP-completitud del problema de satisfacibilidad booleana.^[2]

El descobriment de Karp de que tots estos importants problemes eren NP-complets va motivar l'estudi de la NP-completitud i de l'indagació en la famosa pregunta, de si P = NP.

Els problemes

Mentres que la pertinença del problema SAT o de satisfacibilidad booleana a la classe dels NP-complets va ser demostrada utilisant mecanismes particulars, les pertinences dels 21 problemes següents varen ser demostrades per mig de reduccions polinomiales. Aixina, el problema SAT es va reduir polinomialmente als problemes 0-1 INTEGER PROGRAMMING, CLIQUE i 3-SAT, i estos a la seua volta es varen reduir a atres varis. La llista completa és la que es mostra a continuació. Les sagnies denoten el fet que la NP-completitud del problema va ser demostrada per reducció polinomial del problema en el nivell directament superior. Note que els noms dels problemes estan escrits en lletres mayúscules i corresponen a abreujaments del nom en anglés, com és lo usual; junt a ells, entre paréntesis, s'escriu la traducció del nom en espanyol.

SAT (Problema de satisfacibilidad booleana, per a fòrmules en forma normal conjuntiva)
- 0-1 INTEGER PROGRAMMING (Problema de la programació llineal sancera)
- CLIQUE (Problema del clique, vore també Problema del conjunt independent)
  - SET PACKING (Problema del empaquetamiento de conjunts)
  - VERTEX COVER (Problema de la cobertura de vèrtiços)
    - SET COVERING (Problema del conjunt de cobertura)
    - FEEDBACK NODE SET
    - FEEDBACK ARC SET
    - DIRECTED HAMILTONIAN CIRCUIT (Problema del circuit hamiltoniano dirigit)
      - UNDIRECTED HAMILTONIAN CIRCUIT (Problema del circuit hamiltoniano no dirigit)
- 3-SAT (Problema de satisfacibilidad booleana de 3 variables per clàusula)
  - CHROMATIC NUMBER (Problema de la coloració 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 les seqüències de treball)
        
        PARTITION (Problema de la partició)
        MAX-CUT (Problema del tall màxim)

Despuix d'un temps es va descobrir que molts d'estos problemes podien ser resolts si el seu enunciat es particularizaba a unes certes classes, o podien ser resolts aproximadament en un error màxim d'un cert percentage. No obstant David Zuckerman va demostrar en 1996 que cada u d'estos 21 problemes té una versió restringida d'optimisació que és no aproximable a menos que P = NP, demostrant que la versió de la reducció, donada per Karp, generalisa un tipo específic de reducció per aproximació.^[3]

Vore també

Referències

↑ Richard M. Karp (1972). «Reducibility Among Combinatorial Problems», R. E. Miller and J. W. Thatcher (editors) (ed.). Complexity of Computer Computations, New York: Plenum, pp. 85–103.
↑ Stephen Cook (1971). «The Complexity of Theorem Proving Procedures», Proceedings of the third annual ACM symposium on Theory of computing, pp. 151–158.
↑ David Zuckerman(1996).25(6)
1293–1304.

Referències

Este artícul conté una traducció derivada de «Veintiún problemas NP-completos de Karp» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Richard M. Karp (1972). «Reducibility Among Combinatorial Problems», R. E. Miller and J. W. Thatcher (editors) (ed.). Complexity of Computer Computations, New York: Plenum, pp. 85–103.

[2] Stephen Cook (1971). «The Complexity of Theorem Proving Procedures», Proceedings of the third annual ACM symposium on Theory of computing, pp. 151–158.

[3] David Zuckerman(1996).25(6)
1293–1304.

[1]

[2]

[3]