La classe NP. Què és?
Problema
Tinc una motxilla i un grapat d’objectes. M’agradaria agafar un subconjunt d’aquests objectes que ocupés exactament el volum de la motxilla.
Bé, decidir si ho puc fer o no és un exemple clàssic de problema NP. Tot seguit veurem per què.
Suposem que ja he triat un subconjunt. La comprovació que resta és molt senzilla, només cal fer la suma dels seus volums i mirar si és igual al volum de la motxilla. Però, quantes possibles tries puc fer?
Cada objecte pot ser o no ser a una tria donada. Si tenim N objectes aleshores tenim 2 elevat a N possibles subconjunts (i per tant 2 elevat a N comprovacions com l’anterior).
Aquest nombre és fa exageradament gran a mesura que augmenta el nombre d’objectes (N). Si no em creieu consulteu la història de l’inventor dels escacs i de com va timar al Rei.
Doncs resulta que per aquest problema no hi ha cap estratègia astuta que ajudi a trobar la solució i eviti haver de fer totes les comprovacions. Els programes informàtics que el resolen poden trigar més temps que l’edat de l’Univers fent la prova amb només 100 objectes.
Els problemes com el de la motxilla s’anomenen intractables i ningú dins del món científic confia en poder trobar algun dia un programa que els resolgui de manera eficient.
Però recompensa no faltaria! A més del reconeixement mundial, l’Institut Clay Math ofereix un milió de dòlars a qui ho descobreixi.
Bé, espero que us hagi interessat el tema. Salut!
P.D.: El clàssic joc del buscaminas també és NP!
Tags: R+D