Il problema P contro NP: tra calcolabilità e i limiti della conoscenza

Esistono domande che rimangono aperte per decenni, sfidando la capacità umana di dimostrare ciò che intuitivamente sembra vero. Una di queste è la questione che divide le classi di complessità computazionale P e NP, considerata dal Clay Mathematics Institute uno dei sette problemi del millennio, con un premio di un milione di dollari per chi ne fornisse la soluzione. Eppure, più passano gli anni, più emerge che questa questione matematica nasconde implicazioni filosofiche profonde sul confine tra ciò che possiamo calcolare e ciò che possiamo conoscere.

La natura del problema: quando la verifica è più facile della soluzione

Per comprendere la portata della questione è necessario partire dalle definizioni. I problemi di classe P sono quelli che un computer può risolvere in tempo polinomiale: se l’input ha dimensione n, esiste un algoritmo che produce la soluzione in un numero di passi proporzionale a una potenza di n, come n² o n³. Questi problemi sono considerati “trattabili” o “facili” nel linguaggio della teoria della complessità.

I problemi di classe NP, invece, presentano una caratteristica intrigante: se qualcuno ci suggerisce una soluzione, possiamo verificarne la correttezza in tempo polinomiale, ma trovare quella soluzione potrebbe richiedere un tempo esponenziale, che cresce come 2ⁿ o peggio. Il famoso problema del commesso viaggiatore è l’esempio classico: dato un insieme di città, trovare il percorso più breve che le visita tutte e ritorna al punto di partenza. Verificare che un percorso proposto sia effettivamente il più breve è relativamente semplice, ma trovarlo richiede di confrontare un numero di possibilità che cresce fattoriale con il numero delle città.

La domanda fondamentale che da cinquant’anni tormenta matematici e informatici è: P coincide con NP, oppure i due insiemi sono distinti? Dal momento che ogni problema di P è automaticamente anche in NP (se posso risolverlo, posso anche verificare la soluzione), la questione si riduce a chiedere: esistono problemi che sono intrinsecamente più difficili da risolvere che da verificare? O, come suggerisce l’intuizione formulata da John Nash in una lettera del 1956 al National Security Agency, esistono problemi la cui soluzione richiede davvero un’intelligenza superiore rispetto alla mera verifica?

Le implicazioni di un possibile sì

La maggioranza degli esperti è convinta che P sia diverso da NP, ma non esiste ancora una dimostrazione che lo provi con certezza matematica. Tuttavia, vale la pena esplorare le conseguenze dell’ipotesi opposta, per quanto improbabile: cosa accadrebbe se si dimostrasse che P = NP?

Le implicazioni sarebbero rivoluzionarie. Significherebbe che ogni problema la cui soluzione può essere verificata rapidamente può anche essere risolto rapidamente. La criptografia moderna, che si basa sull’assunto che certi problemi siano computazionalmente intrattabili, crollerebbe. Algoritmi per la progettazione di farmaci, la logistica, l’intelligenza artificiale e la verifica di circuiti elettronici diventerebberi immediatamente molto più efficienti. In un certo senso, dimostrare che P = NP sarebbe come scoprire un algoritmo universale capace di risolvere qualsiasi problema verificabile.

Tuttavia, come osserva Scott Aaronson, teorico della complessità noto per il suo lavoro pionieristico sui limiti quantistici del calcolo, la dimostrazione che P = NP sarebbe solo l’inizio. Conoscere l’esistenza di un algoritmo polinomiale non equivale a conoscerne l’algoritmo stesso. Potremmo dimostrare che esiste una scorciatoia senza sapere dove trovarla, una prospettiva filosoficamente affascinante ma praticamente frustrante.

I confini della dimostrazione e la meta-matematica

Negli ultimi anni, la ricerca ha esplorato una via indiretta per affrontare il problema: invece di cercare di dimostrare direttamente l’uguaglianza o la disuguaglianza, si chiede se una tale dimostrazione sia possibile all’interno di sistemi formali standard. Questo approccio, che combina la teoria della complessità con la logica matematica, ha portato a risultati sorprendenti.

Come riportato in ricerche pubblicate sull’Electronic Colloquium on Computational Complexity (ECCC) nel 2025, esistono teorie della matematica in cui non è possibile dimostrare che P ≠ NP, anche se questa disuguaglianza fosse vera. Questo risultato, che ricorda il famoso teorema di incompletezza di Gödel, suggerisce che il problema P contro NP potrebbe essere in qualche senso indipendente dagli assiomi standard della matematica, proprio come la continuità dell’ipotesi del continuo lo è per la teoria degli insiemi di Zermelo-Fraenkel.

Questa prospettiva cambia radicalmente il modo in cui concepiamo il problema. Non si tratta più solo di trovare l’algoritmo giusto o la dimostrazione corretta, ma di chiedere se la struttura stessa dei sistemi logici in cui lavoriamo sia sufficiente a catturare la verità matematica sui limiti del calcolo. Il problema P contro NP diventa così uno specchio in cui si riflettono questioni più profonde sul rapporto tra verità matematica e dimostrabilità formale.

Intelligenza artificiale e la svolta empirica

Uno sviluppo recente e inaspettato arriva dal campo dell’intelligenza artificiale. La teoria della complessità classica suggerisce che certi problemi dovrebbero essere intrattabili in pratica, eppure gli algoritmi di deep learning e machine learning sembrano trovare buone soluzioni approssimate per problemi che teoricamente richiederebbero tempi esponenziali.

Come ha osservato un recente seminario allo Simons Institute for the Theory of Computing, questa apparente contraddizione ha stimulato il campo della “prova di complessità contro l’intelligenza artificiale”. Alcuni teorici avevano interpretato P ≠ NP come un argomento in principio contro la possibilità dell’intelligenza artificiale: se certi problemi sono intrinsecamente difficili, allora nemmeno una macchina intelligente potrebbe risolverli efficientemente. Ma le scoperte empiriche degli ultimi anni hanno indebolito questo argomento, dimostrando che compiti precedentemente considerati inattaccabili possono ora essere affrontati su istanze di grandissima scala.

Questo non significa che P = NP sia stato dimostrato falso in pratica, ma suggerisce che la complessità teorica non sempre corrisponde all’intrattabilità pratica. Esistono costanti nascoste, proprietà strutturali dei problemi reali, e tecniche di approssimazione che rendono affrontabili compiti che la teoria classica considererebbe impossibili. Questa “barriera alla complessità” sembra più permeabile di quanto si credesse.

Conclusione: la bellezza dell’ignoto

Mezzo secolo dopo la formulazione precisa del problema da parte di Stephen Cook e Leonid Levin, indipendentemente nel 1971, la questione P contro NP rimane aperta. Clay Mathematics Institute attende ancora chi presenti una dimostrazione valida, e la comunità scientifica continua a produrre risultati parziali, generalizzazioni, e connessioni con altri campi della matematica e della filosofia.

La persistenza di questo problema non è un segno di fallimento, ma testimonianza della profondità della domanda che pone. Come scriveva il matematico italiano Linda Pagli nei suoi appunti didattici, il problema P contro NP tocca “i limiti della conoscenza umana” più di ogni altra questione matematica. Ci obbliga a interrogare cosa significhi “conoscere” una soluzione, dove finisce la capacità di calcolo e dove inizia l’intuizione creativa, se esista una differenza fondamentale tra trovare e verificare.

Nel suo silenzio, il problema P contro NP ci ricorda che ci sono confini della conoscenza che non abbiamo ancora raggiunto, e che la matematica, come ogni forma di conoscenza autentica, è fatta tanto di domande quanto di risposte. Forse non è la soluzione a renderlo prezios