Utente:AmaliaSantocchio/sandbox2

Complessità

Introduzione

La teoria della complessità

La teoria della complessità computazionale riguarda la valutazione delle risorse di cui un computer ha bisogno per risolvere un problema: tempo (numero di passaggi in un calcolo) e spazio (quantità di memoria utilizzata). Ci sono problemi nell'informatica, nella logica, nell'algebra e nel calcolo che sono risolvibili dai computer, ma che richiedono quantità di spazio o di tempo irrealizzabili. L'obiettivo della teoria della complessità è quello di classificare i problemi in base alla loro complessità, dando maggior importanza a problemi in applicazioni come la crittologia, la programmazione lineare e l'ottimizzazione combinatoria. Un importante risultato della teoria è che i problemi ricadono in rigide gerarchie quando sono classificati in base alle loro esigenze di spazio e tempo. La teoria ha avuto meno successo nel mettere in relazione le due misure di base; ci sono domande aperte sui problemi risolvibili usando uno spazio ridotto, ma per i quali i migliori algoritmi conosciuti usano il tempo esponenziale. La teoria della complessità computazionale dovrebbe essere distinta da un'altra area chiamata "teoria della complessità", un flusso di ricerca interdisciplinare liberamente definito che prevede complessi sistemi dinamici nel lavoro: la teoria del caos, la vita artificiale. Gran parte di questa ricerca è centrata nell'Istituto Santa Fe nel New Mexico, dove si lavora su "sistemi complessi" di vario tipo. La confusione tra i due campi deriva dal fatto che la parola "complessità" è spesso usata in modi diversi. Un sistema o un oggetto potrebbe essere designato come "complesso" in varie condizioni:

se è costituito da molte parti interagenti;

se è disordinato o presenta un'alta entropia;

se esibisce diversità basate su una struttura gerarchica;
se mostra dettagli su molte scale diverse, come i set frattali.

Alcuni di questi significati di "complessità" sono connessi con la teoria della complessità computazionale, ma solo correlati tangenzialmente, concentrando l’attenzione alle semplici misure quantitative della complessità del tempo e dello spazio dei calcoli. Un'ipotesi di lavoro ampiamente accettata nella comunità informatica teorica è che algoritmi praticamente fattibili possono essere identificati con quelli il cui tempo di esecuzione può essere limitato da un polinomio nella dimensione dell'input. Un algoritmo eseguito nel tempo 10ⁿ per gli input con n simboli sarebbe efficiente e verrebbe descritto come un algoritmo in esecuzione in tempo lineare. Un algoritmo di tempo quadratico viene eseguito nel tempo cn² per qualche costante c, inefficace rispetto un algoritmo di tempo lineare, ma abbastanza pratico per ingressi di dimensioni ragionevoli. Una procedura informatica che richiede tempi esponenziali nella dimensione dell'input, porta rapidamente a tempi di esecuzione non raggiungibili. La velocità di un moderno computer è spesso misurata nella quantità di operazioni numeriche eseguite al secondo; comunemente usato è il numero di operazioni in virgola mobile al secondo. Si suppone di avere una macchina che esegue un milione di operazioni in virgola mobile al secondo, lenta dagli attuali standard del supercomputer. Un algoritmo che richiede n² operazioni per un input di dimensione n richiederebbe solo un quarto di secondo per un input di dimensione 500. Anche se il tempo di esecuzione è limitato da n³, un input di dimensione 500 richiede al massimo 2 minuti 5 secondi. D'altra parte, un algoritmo in esecuzione nel tempo 2ⁿ potrebbe, nel peggiore dei casi, richiedere oltre 35 anni per un input di dimensione 50. Con l’aiuto di una calcolatrice tascabile si può verificare che questa differenza tra crescita polinomiale ed esponenziale è robusta, in quanto un aumento di mille volte della velocità del computer aggiunge solo 10 alla dimensione dell'istanza di problema più grande che è possibile risolvere in un'ora con un algoritmo esponenziale (2ⁿ) di tempo, mentre con un algoritmo di tempo quadratico (n²), il più grande di questi problemi aumenta di un fattore di oltre 30.

La teoria della complessità computazionale ha fornito prove dell'esistenza di problemi computazionali per i quali tale comportamento esponenziale è inevitabile. Ciò significa che per tali problemi ci sono infiniti casi "difficili", per i quali qualsiasi algoritmo che risolve il problema deve impiegare un tempo esponenzialmente lungo.

Una classe interessante e importante è la categoria dei problemi NP-completi, la cui soddisfacibilità della logica proposizionale è il caso più noto. Questi problemi richiedono una soluzione di un certo insieme di vincoli (formule della logica proposizionale, nel caso del problema di soddisfacibilità), dove una probabile soluzione può essere rapidamente verificata per vedere se è davvero una soluzione, ma in generale ci sono molte soluzioni candidate. Come esempio di tale problema, si consideri di voler colorare una mappa grande e complicata con solo tre colori in modo che nessun paese con un bordo comune sia colorato allo stesso modo. Gli unici algoritmi generali noti per tali problemi richiedono tempi di esecuzione lunghi nel caso peggiore, ed è constatato che per loro non esistano algoritmi polinomiali temporali. Questa congettura è formulata come disuguaglianza "P ≠ NP": il problema centrale aperto nell'informatica teorica e nella logica matematica.

Tempo e Spazio nella Computazione

Complessità, tempo e spazio

La teoria della complessità analizza le risorse necessarie a risolvere un problema; le più importanti sono:

tempo, cioè il numero di passaggi in un calcolo prima che la macchina si fermi;
spazio, cioè la capacità di immagazzinare dati di un calcolatore e, in un macchina di Turing, il numero di celle visitate.

Un altro approccio consiste nella misura della complessità di un oggetto in base alla grandezza del più piccolo programma che è in grado di descriverlo.

Notazioni tecniche

Definiamo:

$\mathrm {A}$ un alfabeto finito
$\mathrm {A} ^{*}$ il numero finito di elementi di $\mathrm {A}$
Problema un sottoinsieme di $\mathrm {A} ^{*}$
Istanza un elemento di $\mathrm {A} ^{*}$
Grandezza di un istanza $s$ , e la indichiamo con $|s|$ , la sua lunghezza
$M$ una macchina di Turing
$f$ una funzione da $\mathrm {A} ^{*}$ in $\mathrm {A} ^{*}$ ; la funzione è calcolabile da $M$ se per ogni stringa $s$ appartenente ad $\mathrm {A} ^{*}$ , $M$ si arresta sul valore $f(s)$
$P$ problema risolvibile se esiste un $M$ tale da riuscire a calcolare $f_{P}$ , la funzione caratteristica di $P$

Computabilità

I problemi risolvibili possono essere classificati in base al tempo e allo spazio richiesti per la loro risoluzione. Sia $f_{1}$ una funzione calcolabile, $s_{1}$ una stringa ed $M_{1}$ una macchina di Turing in grado di calcolarla; si dice che $f_{1}$ è calcolabile in un tempo $T(n)$ dopo un certo numero di passaggi indicato con $O(T(|s|))$ e calcolato moltiplicando una costante $c$ e $T(|s|)$ . Quindi $f_{1}$ è una funzione calcolabile se esiste una macchina di Turing tale che data una stringa $s$ si fermi dopo $O(T(|s|))$ riquadri sul suo nastro.

Sia $P_{1}$ un problema; si dice che esso sia risolvibile:

in un tempo $T(n)$ se la sua funzione caratteristica è calcolabile in un tempo $T(n)$ ;
in uno spazio $S(n)$ se la sua funzione caratteristica è calcolabile in un tempo $S(n)$ .

Esempi

Siano $\mathrm {A} _{1}$ un alfabeto composto da due simboli $\mathrm {A} _{1}=\{a;b\}$ , $\mathrm {A} _{1}^{*}$ l'insieme finito delle stringhe composte di $a$ e $b$ , $PAL$ il problema definito lasciando le stringhe palindrome di $\mathrm {A} _{1}^{*}$ ; questo problema è risolvibile in un tempo $n^{2}$ controllando che la prima e l'ultima lettera siano uguali ed eliminandole fino ad azzerare le lettere o lasciarne solo una. Un algoritmo necessita di un numero di passaggi pari a $cn^{2}$ per risolvere il problema, per qualche $c>0$ .

La tabella della verità è risolvibile in uno spazio $n$ e nel tempo $2^{n}$ .

Problemi risolvibili in un tempo polinomiale

La classe dei problemi risolvibili in un tempo polinomiale è una tra le più complesse.

Una funzione $f_{2}$ è calcolabile in un tempo polinomiale se esiste un polinomio $p$ per cui $f_{2}$ è calcolabile in un tempo $p(n)$ .

un problema è risolvibile in un tempo polinomiale se se la sua funzione caratteristica è calcolabile in un tempo polinomiale.

Gerarchie e riduzioni

Un primo risultato della teoria della complessità è l'esistenza di rigide gerarchie tra i problemi. Per esempio, si può dimostrare che ci sono problemi che possono essere risolti nel tempo n², ma non nel tempo n, e teoremi simili valgono per i limiti di spazio sugli algoritmi. Per affermare questo risultato nella sua forma più generale, si introduce il concetto di una funzione costruibile nello spazio. Si dice che una funzione S(n) sia costruibile nello spazio se c'è una macchina di Turing M che è S(n) spacebounded, e per ogni n c'è un input di lunghezza n su cui M usa effettivamente celle a nastro S(n). Tutte le funzioni "ragionevoli" come n, n³ e 2ⁿ sono costruibili nello spazio.Il teorema della gerarchia spaziale, dimostrato da Hartmanis, Lewis e Stearns nel 1965, afferma che se S₁(n) e S₂(n) sono funzioni costruttive spaziali, e S₂ cresce più rapidamente di S₁ asintoticamente, così che:

$\lim _{n\to \infty }inf{\frac {s_{1}(n)}{s_{2}(n)}}$ = 0

allora esiste un problema risolvibile nello spazio S₂(n), ma non nello spazio S₁(n).

I problemi difficili costruiti nelle dimostrazioni dei teoremi della gerarchia sono prodotti dalla diagonalizzazione su classi di macchine, e quindi non direttamente rilevanti per i problemi che sorgono nella pratica. Tuttavia, si può dimostrare limiti inferiori sulla complessità di tali problemi utilizzando la tecnica della riduzione efficiente.

Si formalizza la nozione che un problema può essere ridotto ad un altro nel senso che se avessimo un algoritmo efficiente per il secondo problema, avremmo un algoritmo efficiente per il primo. Sia L₁ e L₂ sono problemi espressi negli alfabeti Σ₁ e Σ₂. L₁ si dice che sia polinomiale-tempo riducibile a L₂. Se esiste una funzione computabile f per il tempo polinomiale da Σ₁* a Σ*₂, tale che per qualsiasi stringa s in Σ₁*, s è in L₁ se e solo se f (s) è in L₂. Altre nozioni di riducibilità possono essere definite variando la classe di funzioni f che implementano la riduzione. L'importanza del concetto sta nel fatto che:

se si ha un algoritmo efficiente che risolve il problema L₂, allora si può usare la funzione f per produrre un algoritmo efficiente per L₁;

se non esiste un algoritmo efficiente per L₁, non può esserci un algoritmo efficiente per L₂.

Si noti che la classe P è chiusa in riduzioni di tempo polinomiali poiché se L₁ è riducibile a L₂ e L₂ è in P, allora anche L₁ è in P. Se C è una classe di complessità, e L è un problema in C, qualsiasi problema in C è riducibile a L, quindi L è detto C-completo. Tali problemi sono i problemi più difficili in C; se qualche problema in C è computazionalmente intrattabile, allora un problema di C-completo è intrattabile. La tecnica di riduzione di un problema a un altro è molto flessibile ed è stata utilizzata per mostrare una grande varietà di problemi in informatica, combinatoria e algebra.

EXPTIME e EXPSPACE

Il teorema della gerarchia temporale implica che ci sono problemi in EXPTIME che richiedono tempi esponenziali per la loro soluzione, indipendentemente dall'algoritmo utilizzato.

Il metodo di riduzione consente di trarre la stessa conclusione per altri problemi. Per esempio, si definiscano gli scacchi generalizzati come un gioco con regole simili agli scacchi standard, ma giocate su una scheda n × n, piuttosto che su una tavola da 8 × 8. Nel 1981 Fraenkel e Lichtenstein usarono la tecnica di riduzione per dimostrare che gli scacchi generalizzati sono EXPTIMEcomplete, computazionalmente intrattabili, come anche i problemi completi di EXPSPACE. Un esempio di un problema di questo tipo nell'algebra classica è fornito dalla parola problema per i semigruppi commutativi. Il problema è posto sotto forma di un insieme finito di equazioni formate da un insieme di costanti usando una singola operazione binaria che si presume sia associativa e commutativa, insieme con un'equazione fissa s = t. Il problema è determinare se s = t sia deducibile dall'insieme di equazioni, assumendo le solite regole per l'uguaglianza.

Nel 1981 Mayr e Meyer hanno dimostrato che questo problema era completo con EXPSPACE: qualsiasi algoritmo che risolva questo problema deve utilizzare una quantità di spazio esponenziale su infiniti input. La logica fornisce anche una fonte fertile di esempi di problemi intrattabili. Sebbene il problema decisionale per le vere frasi della teoria dei numeri sia irrisolvibile, se ci si limita a frasi che coinvolgono solo le costanti 0 e 1, insieme all'identità e al simbolo di addizione, allora c'è un algoritmo per determinare se una tale frase è vera o falso (risultato dimostrato da Presburger nel 1930). Nel 1973 Rabin e Fischer provarono che la complessità intrinseca di questo problema è doppiamente esponenziale. Ciò significa che per qualsiasi macchina che risolve questo problema, esiste una costante c > 0 in modo tale che per infinitamente molte frasi la macchina impiega almeno $2^{2^{cn}}$ per determinare se è vera o meno. Se si aggiunge una quantificazione su insiemi finiti, si possono dimostrare limiti inferiori ancora più potenti. Nell'interpretazione prevista per questa teoria, i quantificatori del secondo ordine spaziano su insiemi finiti di numeri interi non negativi.

Albert Meyer

Il problema decisionale per questa teoria è stato dimostrato risolvibile da Büchi nel 1960, ma la sua complessità intrinseca è molto alta. Albert Meyer avvalorò la tesi secondo il quale un algoritmo che decida questa teoria deve utilizzare per infiniti ingressi di lunghezza n una quantità di spazio che è delimitata dal basso da una funzione esponenziale iterata, dove lo stack contiene almeno dn iterazioni, per un fisso d > 0. Il limite inferiore di Meyer è un risultato asintotico che non esclude una procedura di decisione pratica per frasi di dimensioni praticamente fattibili.

Un ulteriore risultato mostra che i limiti inferiori astronomici possono essere dimostrati per WS1S anche se si limita la lunghezza delle frasi. Una rete o un circuito booleani è un grafo diretto aciclico in cui i nodi sono etichettati con operatori logici come AND, OR, NOT. Tale rete con nodi di input e output designati calcola in modo ovvio una funzione booleana. Meyer e Stockmeyer dimostrarono che qualsiasi rete che decida la verità di tutte le frasi di WS1S di lunghezza 616 o inferiore deve contenere almeno 10123 nodi. Anche se i nodi fossero delle dimensioni di un protone e collegati da fili infinitamente sottili, la rete riempirebbe densamente l'universo conosciuto. Esistono anche problemi intrattabili nell'area delle logiche proposizionali non classiche. L'area delle logiche substrutturali, logica lineare e di pertinenza. Il frammento di congiunzione implicita della logica R delle implicazioni rilevanti fu dimostrato decidibile da Saul Kripke nel 1959 usando un sofisticato lemma combinatorio. Si comprende che questa logica proposizionale non ha una procedura di decisione ricorsiva primitiva, quindi l'intricato metodo di Kripke è essenzialmente ottimale. Questa è forse la logica non classica decidibile più complessa conosciuta.