P CONTRA NP

1. Problema P (difícil de trobar) contra NP (fàcil de verificar):

Aquest problema, plantejat de manera independent el 1971 per Stephen Cook i per Leonid Levin es considera avui dia el problema central de la computació teòrica.

La qüestió és que existeixen, d'una banda, problemes resolubles de manera determinista mitjançant algoritmes polinòmics i en un temps polinomial, com pot ser, per exemple la resolució d'equacions, la realització de sumes, productes, etc., Podent delimitar el temps de resolució, més o menys llarg, d'una manera acceptable. Aquests són els problemes P.No obstant això, també hi ha problemes NP que poden resoldre de manera indeterminista provant una solució conjecturada. Aquesta comprovació és d'una gran rapidesa en comparació amb el temps polinomial necessari en general per a la resolució determinista dels problemes P.

És clar que tot problema P és també NP, és a dir, tot problema resoluble en temps polinomial mitjançant un algoritme adequat (P), és també un problema que admet una comprovació ràpida (NP).

Però, i a l'inrevés?. Hi ha problemes NP que no siguin P?. És a dir, ¿hi ha problemes que admeten una comprovació de solució o no solució conjecturada i, en canvi, no admeten en temps polinomial una resolució algorítmica?


En el càlcul computacional poden presentar problemes on el nombre d'alternatives possibles per a una determinada condició de procés és tan gran que ni tan sols amb les supercomputadors existents encara en la nostra tecnologia es podrien afrontar en tota la vida d'un ésser humà, ja que no tindria per això el suficient temps (és el problema P). En canvi, la verificació que una determinada alternativa verifica la condició de procés és una cosa pràcticament instantani (és el problema NP).


Si, per exemple, volem col·locar 6000 llibres en 200 prestatgeries, de manera que es compleixi la condició que no estiguin junts certs llibres de diferent matèria, ens trobem que el nombre d'alternatives possibles podria superar al nombre d'àtoms de la Via Làctia, amb la qual cosa, el determinar-les totes (problema P - difícil de trobar) és precisament això, molt difícil en l'actual tecnologia de la computació. En canvi, el verificar una d'aquestes alternatives com a vàlida, quan algú conjectura una solució, (problema NP - fàcil de verificar) és immediat. 


En aquests exemples, en què el problema NP és comprovable immediatament, però el problema P sembla no existir, es deu això al fet que realment el problema P no és possible o bé que no es té la tecnologia computacional adequada per a la seva resolució de forma algorítmica en temps polinomial?Aquesta és la pregunta no contestada que dóna consistència al problema.


Entre els exemples actuals més candents hi ha el de la criptografia i la comprovació de claus informàtiques (NP) en contraposició al problema de generació algorítmica de tals claus en un temps polinomial (P).


Si algú troba la resposta que la envie a mariopastorrico@gmail.com i jo la comprove i em porte el milió d'euros que donen per resoldre'l. ;)