P != NP (o no?)

Forse è stata dimostrata la congettura più importante nel campo dell'informatica: alcuni problemi sono intrinsecamente difficili. In attesa che la comunità matematica accetti o no la dimostrazione, ecco una spiegazione di qual è il problema.

Oggi la comunità matematica mondiale è stata scossa da una notizia bomba: un ricercatore dell’HP, Vinoy Deolalikar, ha affermato di avere dimostrato che effettivamente P != NP. Su Good Math, Bad Math, MarkCC fa un rapido resoconto del problema per i matematici non esperti in teoria della complessità. E per chi matematico non è?

(altro…)

Continua sul Post