NP-complet
En teoria de la complexitat computacional, la classe de complexitat NP-complet és el subconjunt dels problemes de decisió en NP tal que tot problema en NP es pot reduir en cada u dels problemes de NP-complet. Es pot dir que els problemes de NP-complet són els problemes més difícils de NP i molt provablement no formen part de la classe de complexitat P. La raó és que de tindre's una solució polinòmica per a un problema NP-complet, tots els problemes de NP tindrien també una solució en temps polinòmic.
Si es demostrara que un problema NP-complet, cridem-ho A, no es poguera resoldre en temps polinòmic, el restant dels problemes NP-complets tampoc es podrien resoldre en temps polinòmic. Açò es deu a que si un dels problemes NP-complets distints de A, digam X, es poguera resoldre en temps polinòmic, llavors A es podria resoldre en temps polinòmic, per definició de NP-complet. Ara, poden existir problemes en NP i que no siguen NP-complets per als quals existixca solució polinòmica, encara no existint solució para A.
Com a eixemple d'un problema NP-complet trobem el problema de la suma de subconjunts que es pot enunciar com seguix: donat un conjunt S de sancers, ¿existix un subconjunt no buit de S els elements de la qual sumixen zero? És fàcil verificar si una resposta és correcta, pero no es coneix millor solució que explorar tots els 2n-1 subconjunts possibles fins a trobar un que complixca en la condició.
Definició de NP-complet
[editar | editar còdic]Un problema de decisió C és NP-complet si:
- C està contingut en el conjunt NP, i
- Tot problema de NP és reducible a C en temps polinomial.
Es pot demostrar que C és NP demostrant que un candidat a solució de C pot ser verificat en temps polinòmic.
Una transformació polinòmica de L en C és un algoritme determinista que transforma instàncies de l ∈ L en instàncies de c ∈ C, tals que la resposta a c és positiva si i només si la resposta a l ho és.
Com a conseqüència d'esta definició, de tindre's un algoritme en P per a C, es tindria una solució en P per a tots els problemes de NP.
Esta definició va ser proposta per Stephen Cook en 1971. Al principi semblava sorprenent que existiren problemes NP-complets, pero Cook va demostrar (teorema de Cook) que el problema de satisfacibilidad booleana és NP-complet. Des de llavors s'ha demostrat que mils d'atres problemes pertanyen a esta classe, casi sempre per reducció a partir d'atres problemes per als que ya s'havia demostrat la seua pertinença a NP-complet; molts d'eixos problemes apareixen en el llibre de Garey and Johnson's de 1979 Computers and Intractability: A Guide to NP-completeness.
Un problema que satisfà la segona condició pertany a la classe NP-hard independentment de que satisfaça la primera.
Història
[editar | editar còdic]El concepte de "NP-complet" va ser introduït per Stephen Cook en un artícul titulat 《The complexity of theorem-proving procedures》 en les pàgines 151-158 de Proceedings of the 3rd Annual ACM Symposium on Theory of Computing en 1971, encara que el terme "NP-complet" com tal no apareix en el document. En la conferència de ciències de la computació va haver un intens debat entre els científics de la computació sobre si els problemes NP-complets podien ser resolts en temps polinòmic o en una màquina de Turing determinista. John Hopcroft va dur a tots els assistents de la conferència a consens concloent que l'estudi sobre si els problemes NP-complets són resolubles en temps polinòmic deuria ser pospost ya que ningú havia conseguit provar formalment les seues hipòtesis ni en un sentit ni en un atre. Açò es coneix com el problema ¿P=NP?.
Ningú ha segut capaç encara de donar una resposta final a este problema, fent-ho un dels grans problemes no resolts de la matemàtica. Des de maig de 2000, el Clay Mathematics Institute oferix una recompensa d'un milló de dólars a qui conseguixca donar una demostració de que P=NP o P≠NP.
El Teorema de Cook demostra que el problema de satisfacibilidad booleana és un problema NP-complet. En 1972, Richard Karp va demostrar que atres problemes eren també NP-complets (vore Llista de 21 problemes NP-complets de Karp). A partir dels resultats originals del Teorema de Cook, s'han descobert centenars de problemes que també pertanyen a NP-complet per mig de reduccions des d'atres problemes que prèviament s'havien demostrat NP-complets; molts d'estos problemes han segut arreplegats en llibre de 1979 de Garey and Johnson's Computers and Intractability: A Guide to NP-Completeness.
Vore també
[editar | editar còdic]Referències
[editar | editar còdic]- Garey, M. and D. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1979. ISBN 0-7167-1045-5 (Est és un llibre clàssic que desenrolla la teoria i classifica molts dels problemes NP-complets)
- S. A. Cook, The complexity of theorem proving procedures, Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York, 1971, 151-158
- Complexitat computacional de jocs i trenca-caps
- Tetris és difícil, encara per a aproximar-ho
- ¡Buscaminas és NP-complet!
- Llista de problemes NP-complet
- Este artícul conté una traducció derivada de «NP-completo» 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.