E se vi dicessi che tutto quello che credevate di sapere sulla difficoltà dei problemi computazionali è, potenzialmente, basato su una bugia?
No, non è il solito hype da lunedì mattina per vendere qualche nuovo framework JavaScript che morirà tra tre mesi. Stiamo parlando di qualcosa di molto più profondo, che scava nelle fondamenta stesse della logica e della complessità. È emersa una notizia che sta facendo saltare sulla sedia i pilastri della computer science: l’ipotesi del tempo esponenziale (ETH – Exponential Time Hypothesis) potrebbe essere falsa.
Per chi non ha passato le ultime notti a debuggare algoritmi impossibili, lasciate che vi spieghi la questione senza usare troppi termini accademici che fanno venire il mal di testa. L’ETH è quel presupposto (molto comodo, per la verità) secondo cui certi problemi sono intrinsecamente difficili e richiedono un tempo che cresce in modo esponenziale rispetto alla dimensione dell’input. In pratica, è la scusa perfetta per dire: «Non è che il mio codice fa schifo, è che il problema è computazionalmente impossibile da risolvere in tempi umani». Se l’ETH cade, crolla un intero castello di certezze su quanto sia difficile risolvere problemi di logica o di soddisfacibilità (SAT).
Immaginate di trovarvi in un film di Christopher Nolan, dove improvvisamente scoprite che le leggi della fisica che vi tenevano intrappolati in un loop temporale erano solo un errore di calcolo. Se questo nuovo studio dimostra che possiamo aggirare quella barriera esponenziale, le implicazioni sono enormi. Potremmo trovarci davanti a nuovi modi per ottimizzare la crittografia, la pianificazione logistica o la simulazione di sistemi complessi.
Naturalmente, restiamo con un piede in terra. Siamo in un’epoca in cui ogni minima variazione in un paper scientifico viene subito inghiottita dai motori di ricerca e trasformata in titoli sensazionalistici. Non è che domani mattina la vostra istanza Docker girerà istantaneamente su un vecchio Raspberry Pi. Però, l’idea che ci sia un margine di errore nelle nostre fondamenta matematiche è la cosa più eccitante che potesse capitare in un periodo di stagnazione creativa.
Certo, non aspettatevi che le leggi europee sulla regolamentazione dell’AI cambino domani in base a questa scoperta; la burocrazia di Bruxelles si muove con la velocità di un kernel che sta facendo il reboot. Ma per noi che amiamo smontare i concetti e vedere cosa c’è sotto il cofano, questa è benzina pura. La scienza non è fatta di certezze assolute, ma di tentativi di smontare le certezze altrui. E oggi, qualcuno ha appena trovato un cacciavite molto potente.
Source: Three new discoveries in mathematics, computer science, and physics