Finora abbiamo parlato di calcolabilità e abbiamo stabilito che esistono almeno 3 grandi classi di problemi:
- i problemi risolubili, rappresentati da funzioni calcolabili totali o insiemi ricorsivi
- i problemi semi-decidibili, rappresentati da funzioni calcolabili o insiemi ricorsivamente enumerabili
- i problemi non decidibili, rappresentati da funzioni non calcolabili o insiemi non ricorsivamente enumerabili.
Quindi sappiamo ben classificare la risolubilità di un problema in base all’esistenza o meno di una funzione calcolabile (totale o parziale) che lo risolve. Questa classificazione, però non ci dice nulla riguardo a quanto costa trovare una soluzione ad un problema che so essere decidibile, perché un problema può essere decidibile, ma calcolare la sua funzione può risultare estremamente costoso, tanto da renderne impraticabile la risoluzione in “tempi umani”.
Per questi motivi oggi passiamo a studiare la sola classe dei problemi decidibili più da vicino per arrivare ad una classificazione dei problemi decidibili in base al costo che richiede la loro risoluzione, limitandoci ai soli problemi di decisione, cioè quei problemi che ammettono un algoritmo che ne calcola la funzione caratteristica.
Ci limiteremo anche a calcolare i costi degli algoritmi in base ai loro costi in risorse quali tempo e spazio, anche se esistono altre metriche come il consumo energetico o la quantità di dati trasferiti in una rete e chi più ne ha più ne metta.
Per queste analisi ci serve di considerare il costo per ogni caso del problema in funzione dei suoi dati di ingresso, o meglio della loro taglia. La taglia del dato di ingresso x che rapprentiamo con |x|, verrà opportunamente misurata in base ad alcuni criteri come la stima dell’occupazione in memeria del dato stesso.
Parlando in termini di insiemi: abbiamo un problema formalizzato dall’insieme I,
cercheremo una funzione f(|x|) che esprima la quantità di risorse in spazio o
tempo necessaria al calcolo della soluzione di \(x \in I\)
, anche detto
caso x di I.
Dato che andremo a studiare come cresce l’uso di risorse al crescere della taglia dell’input in modo asintotico, quella che delineeremo è una teoria della complessità asintotica.
In altre parole cercheremo la risposta alla domanda
qual è il modo piú efficiente di risolvere un problema?
Non risponderemo direttamente a questa domanda, ma cercheremo di individuare gruppi di problemi simili e i loro algoritmi risolutori che si trasformano gli uni negli altri mediante opportune funzioni di riduzione.
Per far ciò è necessario prima studiare come si possono esprimere limiti
alle risorse necessarie al calcolo: come si definisce e quali proprietà ha una
funzione \(f:\mathbb{N} \mapsto \mathbb{N}\)
) che sia in grado di
stimare la quantità minima di risorse necessarie per risolvere un certo
problema I. Fra tutte le funzioni possibili, sceglieremo la minima delle funzioni
che maggiorano la quantità di risorse necessarie al calcolo di x ∈ I.
Trovata la funzione f(|x|) che stima le risorse necessarie al calcolo di x ∈ I, diremo piuttosto imprecisamente che il problema I ha complessità in tempo o spazio f. Dato che questa proprietà vale per ogni caso del problema, icluso il caso più difficile, ci stiamo riferendo alla complessità al caso pessimo.
Per determinare la funzione f, è necessario considerare tutti gli algoritmi che risolvono il problema I, che sappiamo essere tanti quanti i numeri naturali (infiniti numerabili). Data una certa funzione f, si può definire una classe di complessità a cui appartengono tutti quei problemi per cui esiste almeno un algoritmo che li risolve e che richiede risorse in misura inferiore o uguale a f(n).
Vedremo problemi ardui e problemi completi, che sono i piú ardui da risolvere con quelle limitazioni spazio/temporali.
Già sappiamo (conoscenza pregressa di tutti gli informatici) che esistono due classi di complessità molto importanti:
- Ptime o semplicemente \(\mathcal{P}\)
, la classe dei problemi risolubili in tempo polinomiale deterministico, che viene associata alla classe dei problemi “tratabili”
- NPTime o semplicemente \(\mathcal{NP}\)
, la classe dei problemi risolubili in tempo polinomiale non-deterministico, che viene associata alla classe dei problemi “intrattabili”
Il termine polinomiale deterministico o non-deterministico verrà spiegato meglio più avanti, ma ha a che fare con le Macchine di Turing deterministiche e non deterministiche, che abbiamo già incontrato. La differenza formale che c’è tra i due modelli è che una macchina deterministica impiega una funzione di transizione, mentre quella non deterministica impiega una relazione di transizione.
Inoltre, in analogia con la tesi di Church e Turing, esiste la tesi di Cook e Karp che stabilisce questa associazione: P = trattabile e NP = non trattabile.
I risultati della teoria della complessità che andremo a enunciare sono invarianti rispetto al modello di calcolo scelto. Ci poniamo cioè l’obbiettivo di avere una teoria robusta.
Le classi di complessità formano una gerarchia? Questo è il frammento che vedremo noi:
È noto anche che \(\mathrm{LOGSPACE} \subset \mathrm{PSPACE}\)
, ma non è
noto se \(\mathcal{P} \subset \mathcal{NP} \text{ oppure }
\mathcal{P} = \mathcal{NP}\)
che è uno dei 7 problemi per il millennio e non
è neppure noto se sia dimostrabile.
Siamo riusciti a mostrare che \(R \subset RE\)
perché non avevamo alcuna
limitazione sul dispendio di risorse, mentre per P e NP la stessa tecnica
fallisce perché i problemi in entrambi gli insiemi sono decidibili, ma lo sono
in tempo limitato.