Qualche tempo fa, in questo articolo, abbiamo parlato degli algoritmi e della loro complessità temporale, cioè la stima del tempo impiegato da un algoritmo per terminare. Per farlo abbiamo introdotto la notazione O grande che lega la dimensione dell’ingresso al tempo necessario per produrre l’uscita. Oggi faremo un passo avanti e tratteremo la teoria della complessità computazionale, la teoria più importante dell’algoritmica, e per comprenderla è necessario aver capito proprio la notazione O grande: l’idea di base, quella da tenere a mente, è che esistono problemi facili e problemi difficili.

Problema in forma di riconoscimento

Prima di affrontare la teoria conviene considerare una particolare categoria di problemi, quelli nella cosiddetta forma di riconoscimento. Un problema di questo tipo è apparentemente semplice: ha solo due possibili soluzioni, e no. Ad esempio:

Dato un insieme I di n elementi, esiste un suo sottoinsieme S i cui elementi soddisfano una certa caratteristica C?

Questa domanda ha solo due possibili risposte, sì e no, ma se volessimo avere di più?

Dato un insieme I di n elementi, trovare un suo sottoinsieme S i cui elementi soddisfano una certa caratteristica C.

È abbastanza evidente che i due problemi si somigliano molto e in effetti si può dimostrare che modificando opportunamente il primo si può rispondere facilmente al secondo. Conviene quindi concentrarsi sui problemi in forma di riconoscimento in quanto sono più semplici da trattare nella teoria, tenendo a mente che grazie a essi si possono risolvere anche problemi più complessi.

Classe P

Ipotizziamo di avere un problema P1 e di aver progettato un algoritmo in grado di risolverlo. Se questo algoritmo termina in tempo O(f(n)) con f(n) polinomio, allora P1 si dice problema polinomiale, o facile. In sostanza f(n) deve essere nella forma nk con k∈ℜ e tutti i problemi risolvibili in modo efficiente con questa complessità formano la cosiddetta classe P. La moltiplicazione in colonna, avendo complessità O(n2), rientra proprio in questa classe. Un momento, nell’articolo menzionato all’inizio era scritto che “Da n2 in su l’algoritmo è pessimo”, quindi come è possibile che un algoritmo con O(n15) sia considerato efficiente? Nella pratica non è così ma nella teoria va tutto bene perché esistono complessità ben peggiori.

Classi NP e co-NP

Ora ipotizziamo di avere un problema P2 risolvibile con un algoritmo in un tempo molto lungo, ad esempio con O(2n), cioè con f(n) esponenziale. Un problema del genere richiede secoli per essere risolto, però possiamo introdurre uno strumento che ci permette di verificare se una possibile soluzione è corretta oppure no. Si definisce allora il cosiddetto certificato polinomiale, un’informazione ausiliaria che permette di verificare in tempo polinomiale la correttezza della risposta dato un certo input. Non è importante come questo certificato sia stato ottenuto, ma il fatto che esista. Ora possiamo definire la classe NP (Nondeterministic Polynomial): è la classe di problemi che ammettono un certificato polinomiale per ogni istanza con risposta .

Ad esempio:

Dato un grafo G=(V,E), questo contiene un cammino hamiltoniano?

appartiene a questa classe. Anche la scomposizione in fattori primi alla base della moderna crittografia, che ha complessità esponenziale, appartiene alla classe NP. Infatti se ci chiediamo “Il numero xxx è scomponibile in fattori primi?” e diciamo “Sì, lo è”, dobbiamo anche essere in grado di dimostrarlo in modo rapido, grazie proprio al certificato. In questo caso il certificato può essere una fattorizzazione di xxx: moltiplicando i fattori tra di loro si ottiene proprio il numero xxx, dimostrando che effettivamente questo numero è fattorizzabile. La moltiplicazione è, come abbiamo detto, un problema polinomiale, quindi il certificato è polinomiale e abbiamo dimostrato che la scomposizione in fattori primi è un problema NP. Ma se non abbiamo un vero certificato tra le mani, come si fa? Non ha importanza, basta sapere che almeno esiste, non è necessario conoscerlo.

Esiste anche la classe co-NP, i cui problemi ammettono un certificato polinomiale per ogni istanza con risposta no. I problemi della classe P ammettono certificati polinomiali sia per il sì sia per il no, quindi hanno certificato vuoto e in pratica appartengono sia a NP sia a co-NP.

Dettaglio sulla crescita della complessità temporale.

Riduzione polinomiale e NP-completezza

È abbastanza intuitivo il fatto che alcuni problemi della classe NP sono intrinsecamente più difficili di altri, quindi consideriamo due problemi P3 e P4 con P4 più difficile di P3. Se conosciamo un algoritmo veloce per P4, possiamo sfruttarlo per risolvere P3 tramite opportune ipotesi e possiamo ricorrere alla riduzione polinomiale. P3 si riduce in tempo polinomiale a P4, cioè P3∝P4, se esiste un algoritmo per P3 che utilizza un numero polinomiale di volte un algoritmo per P4 come procedura black-box, cioè senza conoscerne i dettagli realizzativi e senza modificarne i parametri. In pratica sfruttiamo il metodo per risolvere un problema molto difficile e con opportune modifiche lo adattiamo a un problema più semplice.

Qualcuno avrà già pensato a dove voglio andare a parare: se riusciamo a trovare un problema P* molto difficile, tale che tutti gli altri problemi della classe NP sono riducibili a P*, abbiamo in mano una soluzione universale: basta risolvere in modo efficiente P* e automaticamente, grazie alla riducibilità polinomiale, possiamo risolvere efficientemente tutti i problemi della classe NP. Un problema P* di questo tipo si chiama NP-completo. Ma un problema del genere esiste? S.A. Cook, nel 1971, ha dimostrato che esistono problemi NP-completi, e in particolare ha dimostrato che il problema di soddisfacibilità booleana (cioè, data una formula booleana, determinare se può assumere il valore vero) appartiene a questa categoria. Attualmente esistono centinaia di problemi NP-completi, quindi basterebbe risolverne uno solo per poter risolvere anche tutti gli altri problemi della classe NP.

P=NP?

Ma allora esiste un algoritmo efficiente (cioè polinomiale) in grado di risolvere uno dei problemi NP-completi? Al momento no e gli addetti ai lavori sono quasi tutti d’accordo sul fatto che non esista. Ma cosa succederebbe se un giorno qualcuno riuscisse a trovarlo? Per dirla in termini tecnici: sarebbe un bel casino, sia in senso buono sia in senso cattivo. Tutte le applicazioni basate sulla crittografia diventerebbero inutili: conti bancari e comunicazioni private sarebbero alla mercé di chiunque, si potrebbero spegnere i sistemi di sicurezza delle centrali nucleari e i motori degli aerei in volo, causando delle catastrofi di proporzioni inaudite. Ma c’è anche un aspetto positivo perché la ricerca subirebbe un’accelerazione incredibile grazie alla potenza delle simulazioni e delle elaborazioni: nuove cure a malattie attualmente incurabili, creazione di nuovi materiali e nuove teorie attualmente inavvicinabili.

La ricerca è aperta ma per quanto ne sappiamo una soluzione definitiva è ancora lontana.