P ≠ NP!

09-08-2010 13:00 - Fonte: www.ossblog.it

P è uguale a NP? Secondo il ricercatore Vinay Deolalikar la risposta definitiva è no. Per chi non ha conoscenze di complessità computazionale: In questa teoria, la classe P consiste di tutti quei problemi di decisione che possono essere risolti con una macchina sequenziale deterministica in un tempo che è polinomiale rispetto alla dimensione dei dati di ingresso; la classe NP consiste di tutti quei problemi di decisione le cui soluzioni positive possono essere verificate in tempo polinomiale avendo le giuste informazioni, o equivalentemente, la cui soluzione può essere trovata in tempo polinomiale con una macchina non deterministica. Un problema che espresso in questo modo può sembrare particolarmente contorto per i profani, ma che ha un’importanza talmente vasta da essere entrato a far parte dei 7 problemi matematici del millennio, un grande dilemma dell’informatica teorica. I primi commenti sulla qualità della dimostrazione, un documento da un centinaio di pagine, parlano di una ricerca solida che potrebbe essere la soluzione cercata da molti. Per le persone normali non cambierà molto, ma finalmente possiamo avere la certezza che esistono dei problemi che si possono calcolare solo in tempi non deterministici, ma verificare in tempi polinomiali. Le fondamenta della crittografia. Foto | Wikipedia Via | GregBaker P ≠ NP! é stato pubblicato su ossblog alle 13:00 di lunedì 09 agosto 2010.

- Continua...