Questo articolo serve da preludio al prossimo articolo, in cui spieghiamo la distinzione tra classi di complessità computazionale P, NP, ecc. Questi nomi si riferiscono a problemi decisionali. In questo articolo vediamo cosa significa e in particolare come convertire in problemi decisionali i soliti problemi che ci interessa risolvere.
Un concetto fondamentale è quello di complessità computazionale. Dato un input di dimensione $n$, la complessità computazionale è (informalmente) il tempo necessario per completare l’algoritmo come funzione di $n$. Tipicamente non ci interessa considerare la formula in maniera esatta, ma ci interessa solo il suo andamento asintotico. Ad esempio, supponiamo di voler moltiplicare due matrici $N \times N$, che chiamiamo $A$ e $B$. La formula per gli elementi di $C=AB$ è data da
$$C_{ij} = \sum_{k=1}^N A_{ik} B_{kj}$$
Poiché moltiplicare è molto più costoso che sommare, ci interessa solo il numero di moltiplicazioni. In tal caso per ogni elemento di $C_{ij}$ dobbiamo effettuare $N$ moltiplicazioni, e poiché $C$ ha $N^2$ elementi, abbiamo bisogno di $N^3$ moltiplicazioni. La complessità computazionale dell’algoritmo è perciò $\mathcal{O}(N^3)$. Ciò non vuol dire che ciò è quanto di meglio si possa fare: in particolare, per questo problema esiste un algoritmo che risolve il problema con complessità $\approx\mathcal{O}(N^{2.8})$ (in maniera simile a quanto abbiamo visto in un articolo precedente per la moltiplicazione dei numeri complessi). Non è noto quale sia la complessità ottimale. Questo per dire che per risolvere lo stesso problema potrebbero esistere algoritmi diversi con complessità computazionali diverse.
Si dice che un algoritmo la cui complessità è della forma $\mathcal{O}(n^k)$ per un qualche $k$, dove $n$ è la grandezza dell’input, ha tempo “polinomiale”. La moltiplicazione tra matrici ha tempo polinomiale nella dimensione delle matrici. A livello pratico “tempo polinomiale” vuol dire “risolvibile in maniera efficiente”, anche se ci sono dei caveat: ad esempio se $k$ è enorme, l’algoritmo è praticamente inutile; oppure se la costante implicita nell’$\mathcal{O}$ è enorme è anche in questo caso inutile (in qual caso si dice “algoritmo galattico“).
Al contrario possiamo avere ad esempio algoritmi con complessità esponenziale (cioè $\mathcal{O}(2^{cn})$) oppure fattoriale (cioè $\mathcal{O}(n!)$), oppure qualsiasi altra forma. Tipicamente qualsiasi cosa sia esponenziale o peggio è considerato “inefficiente” per $n$ anche solo moderatamente grandi. Anche qui ci vogliono dei caveat: ad esempio se $c$ è minuscolo, anche un algoritmo esponenziale può essere efficiente. In pratica questi caveat sono molto rari, e questo rende la distinzione tra algoritmi polinomiali ed esponenziali utile concretamente.
Tornando alla questione iniziale, un problema decisionale è semplicemente un problema la cui soluzione è una risposta sì o no. Ad esempio la domanda: “il numero $k$ divide $n$?” è un problema decisionale, mentre invece il problema della moltiplicazione tra matrici, almeno come formulato sopra, non lo è.
L’importanza dei problemi decisionali è dovuta in parte al fatto che è spesso possibile convertire molti problemi in problemi decisionali. Un caso concreto è il problema del commesso viaggiatore. Invece di cercare il percorso ottimale (come nella formulazione solita), chiediamo la domanda: “esiste un percorso di lunghezza inferiore ad $l$?”.
Un altro esempio è la fattorizzazione di un intero: dato un intero $N$, trova i fattori primi di $N$. Una maniera di trasformare questo problema in uno decisionale è porre la domanda: “Esiste un fattore primo di $N$ minore di $k$?”. In particolare, supponiamo di saper risolvere il problema decisionale. Allora possiamo usare la ricerca binaria nell’intervallo $[0, \sqrt{N}]$ partendo da $k\approx\sqrt{N}/2$ per trovare un fattore primo. La ricerca binaria richiede un tempo $\mathcal{O}(\log_2 N)$ che è polinomiale nel numero di bit di $N$ (che è appunto $n \approx \log_2 N$).
Al contrario un problema decisionale che potrebbe sembrare equivalente, ma non lo è, è il seguente: “dati $p$ ed $N$, $p$ divide $N$?”. Questo problema può essere risolto banalmente dividendo i due numeri, che richiede solo $\mathcal{O}(1)$. Tuttavia non ci aiuta a fattorizzare $N$, perché richiede tempo esponenziale per essere convertito nel problema originale. Per utilizzare il problema decisionale, dobbiamo in questo caso chiamare il problema decisionale per ogni intero $\leq \sqrt{N}$ (nel caso peggiore proprio $\approx \sqrt{N}$ volte) e quindi la complessità della conversione è $\mathcal{O}(\sqrt{N})$, che è esponenziale nel numero di bit di $N$.