NP depth

Ultimamente ho ripreso a leggere questa interessante rivista pubblicata dal MIT. Ed ho ritrovato, tra i blog collegati, quello di Scott Aaronson.

Aaronson, professore al MIT, è un po una via di mezzo tra l'informatico e il fisico. Si occupa di complessità e quantum computing, un ramo di ricerca avvincente e nuovo.
Il bello del suo blog è che mescola concetti semplici di facile comprensione, a quelli tra i più profondi dell'informatica teorica e meccanica quantistica.

Tra i suoi ultimi post si trova questo pezzo, in cui dice del perché il problema P vs NP è il più profondo dei 7 (ora 6) proposti dalla Clay Mathematics Institute:

Apparently the mathematicians had to debate whether P vs. NP was “deep” enough to include in their list. Personally, I take it as obvious that it’s the deepest of them all. And the reason is this: if you had a fast algorithm for solving NP-complete problems, then not only could you solve P vs. NP, you could presumably also solve the other six problems. You’d simply program your computer to search through all possible proofs of at most (say) a billion symbols, in some formal system like Zermelo-Fraenkel set theory. If such a proof existed, you’d find it in a reasonable amount of time. (And if the proof had more than a billion symbols, it’s not clear you’d even want to see it!)

Da come la scrive, sembra una cosa ovvia.
A me sembra come quando qualcuno ti spiega un algoritmo. Ti sembra di aver capito, ma poi vai a scriverlo e non sai da dove cominciare.
Nel leggere il post di Aaronson immaginavo: "Ok, facciamo finta di avere un programma Black-Box che risolve efficentemente un problema NP, ad esempio 3-SAT. Adesso scriviamo un attimo un programma che cerchi tra tutti i teoremi di al più un miliardo di simboli, che utilizzi la Zermelo-Fraenkel Set Theory ..."


Se non sai spiegarlo, probabilmente non lo conosci a fondo.




PS bellissimo anche questo post: i 10 motivi per cui credere che P != NP