Complessità computazionale

"Il software diventa più veloce con maggior lentezza rispetto a quanto lo fa l'hardware" Legge di Wirth

Modelli formali e complessità

Introduzione

La complessità è un argomento di grande importanza per lo studio degli algoritmi. Essa indica quanto un algoritmo è veloce rispetto ad un altro algoritmo che risolve lo stesso problema, e quantifica le risorse (in genere il tempo) necessario per trovare una soluzione ad un certo problema. Sebbene la velocità hardware dei calcolatori sia in costante aumento, gli algoritmi per risolvere una certa classe di problemi continuano (e forse continueranno in futuro) ad essere troppo lenti. Spesso l'impiego di un algoritmo più veloce permette di ridurre drammaticamente il tempo di risoluzione di un problema, in modo superiore rispetto all'impiego di un hardware più performante.

Per poter quantificare con precisione la complessità di un algoritmo è necessario impiegare un'astrazione per poter definire il numero di operazioni compiute da un computer astratto per risolvere un algoritmo. Il numero di operazioni dipende naturalmente dalla dimensione dei dati in ingresso. Ad esempio, il riordino di 100 elementi impiegherà minor tempo rispetto al riordino di 1000 elementi. Tuttavia è interessante misurare come il tempo di esecuzione è in funzione al numero di elementi, in altre parole si vuole trovare una funzione che leghi il numero n di elementi e il tempo t per riordinarli.

Nella teoria della computazione sono stati introdotti vari formalismi, che permettono di modellare un generico calcolatore.

Un vocabolario o alfabeto V è un insieme finito di oggetti detti simboli. Una stringa di V è una sequenza finita di simboli di V. La concatenazione di due stringhe x e y appartenenti a V è una stringa costituita da tutti i simboli di x e tutti i simboli di y. Per ogni alfabeto, l'insieme di tutte le stringhe possibili è indicata con V*.

Un linguaggio L di un alfabeto V è un sottoinsieme di V*, ovvero un sottoinsieme di tutte le stringhe di V. La concatenazione L M di due linguaggi L e M è un linguaggio contenente tutte le stringhe di L.

Macchine a stati finiti

Una Macchina a Stati Finiti (detta anche FSM - Finite State Machine oppure Automa a Stati Finiti) è un formalismo definito da una tripla <Q, I, δ>, dove

  • Q è un insieme finito di stati
  • I è un insieme di simboli d'ingresso
  • δ è detta funzione di transizione e definita come $\delta : QxI \rightarrow Q$

Una FSM può essere visualizzata attraverso un grafo, i cui nodi sono gli stati e gli archi sono le transizioni tra uno stato e l'altro. In modo meno formale, una FSM è un dispositivo astratto che contiene un insieme di stati. Inizialmente si trova nello stato iniziale $Q_0$ , ed in base al simbolo che si trova in ingresso, può modificare il suo stato. L'ingresso, costituito da una stringa di simboli, determina lo stato in cui si troverà la macchina al termine dell'elaborazione.

af001.png

Una transizione da uno stato Q1 a Q2 avviene se è presente un simbolo $i \in I$ tale che $\delta (Q_1, i) = Q_2$ e se lo stato corrente è Q1. In genere esiste uno stato iniziale Q0 e uno o più stati finali appartenenti a Q. Si dice che una FSM "accetta" o "riconosce" un ingresso se, fornendo quel dato ingresso, la FSM termina in uno stato finale Qf. In pratica, una stringa di simboli può essere verificata come "corretta" o "errata" in base allo stato finale raggiunto dalla FSM.

Una FSM "modificata", detta anche Trasduttore a Stati Finiti è definita come un 7-pla <Q, I, δ, Q0, F, O, η>, dove Q, I, δ hanno significato analogo a quello descritto nelle FSM.

  • $Q_0 \in Q$ è un insieme finito di stati
  • $F \subseteq Q$ è un insieme di simboli d'ingresso
  • O è l'insieme dei simboli di uscita
  • $\eta$ è detta funzione di transizione e definita come $\eta : QxI \rightarrow O$

Un Trasduttore a Stati Finiti è quindi una FSM che produce un'uscita associata alle transizioni. Nel grafo, il simbolo d'uscita viene associato all'arco corrispondente alla transazione, quindi un arco contiene il simbolo d'ingresso accettato e il simbolo d'uscita prodotto. Una transizione da uno stato Q1 a Q2 avviene se lo stato corrente è Q1 ed è presente un simbolo $i \in I$ tale che $\delta(Q_1, i)=Q_2$. Inoltre, se si ha $\eta(Q_1, i)=o$ allora viene scritto il simbolo o in uscita.

af002.png

Un Trasduttore a Stati Finiti quindi trasduce una stringa di input in una stringa di output.

Macchine di Turing

Una Macchina di Turing è un formalismo introdotto da Alan Turing di fondamentale importanza per l'informatica teorica, ed è definito come una 9-pla $< Q, I, \Gamma, O, \delta, \eta, Q_0, Z_0, F >$ dove:

  • Q è un insieme finito di stati
  • I è un insieme di simboli d'ingresso
  • $\Gamma$ è un insieme di simboli di memoria
  • O è un insieme di simboli d'uscita
  • $F \subseteq Q$ è l'insieme degli stati finiti
  • $Q_0 \in Q$ è lo stato iniziale
  • $Z_0 \in \Gamma$ è il simbolo iniziale della memoria
  • $\delta$ è la funzione di transizione, definita come $\delta : (Q-F)xIx\Gamma^k \rightarrow Qx\Gamma^kx\lbrace R, L, S \rbrace^{k+1}$
  • $\eta$ è la funzione d'uscita, definita come $\eta : (Q-F)xIx\Gamma^k \rightarrow Ox\lbrace R, S \rbrace$

Una MT è costituita da:

  • un nastro di ingresso Ti
  • un nastro di uscita To
  • k nastri di memoria T1 ,…,Tk
  • un dispositivo di controllo con un numero finito di stati

Per "nastro" si intende una sequenza di locazioni di memoria, che possono contenere dei simboli o dati. Il nastro di ingresso è quindi costituito da una sequenza di simboli in ingresso, e analogamente il nastro di uscita contiene una sequenza di simboli di output. Il dispositivo di controllo possiede un "puntatore" o testina di lettura per ogni nastro, che è posizionata su una data locazione di memoria. Ogni testina di memoria può leggere e/o scrivere un simbolo ed essere spostata a destra, a sinistra e rimanere ferma. La testina del nastro Ti legge l'ingresso, e non può scrivere mentre la testina del nastro To può solo scrivere ed essere spostata a destra.

mt001.png

Il dispositivo di controllo comprende un numero finito di stati, a cui sono associate delle transizioni. Le transizioni sono in funzione del simbolo d'ingresso e dei simboli di memoria presenti sui k nastri di memoria. Ad ogni transizione la MT effettua le seguenti operazioni:

  • scrive simboli nei nastri di memoria
  • scrive un simbolo l'uscita nel nastro d'uscita To
  • muove una o più testine di memoria a destra, a sinistra o non le muove. La testina di uscita può rimanere ferma o spostarsi a destra

In tutto sono presenti k+2 nastri (k nastri di memoria, un nastro d'ingresso e uno d'uscita), ed inizialmente l'unità di controllo si trova nello stato iniziale Q0 . I nastri di memoria inizialmente contengono un simbolo Z0 , mentre il nastro di uscita è vuoto. Le testine delle memoria sono posizionate sul simbolo iniziale.

Anche una MT può essere rappresentata da un grafo, analogamente alle FSM, contenente i nodi che rappresentano gli stati e gli archi che corrispondono alle transizioni. Ogni transizione è associata ad un simbolo d'ingresso, un insieme di k simboli di memoria letti da ognuno dei nastri di memoria. Durante la transizione, la MT cambia stato, scrive eventuali simboli sui k nastri di memoria, effettua gli spostamenti delle k testine sui nastri di memoria a destra o a sinistra (oppure non le sposta), scrive un simbolo nel nastro d'uscita ed eventualmente sposta la testina del nastro d'ingresso. Una transizione è quindi definita come:

i, <s1 , …, sk> / o, <s'1 , …, s'k>, <M1 , …, Mk>

dove:

  • i simbolo d'ingresso
  • s1 , …, sk simboli letti nei nastri di memoria
  • o simbolo d'uscita
  • s'1 , …, s'k simboli scritti nei nastri di memoria
  • M1 , …, Mk spostamenti delle k testine. M può essere L (spostamento a sinistra), R (spostamento a destra), oppure S (nessun spostamento)

La funzione di transizione genera lo stato successivo, i simboli di memoria da scrivere nei nastri e gli spostamenti delle testine. La funzione di uscita produce il simbolo d'uscita e lo spostamento della testina d'uscita.

Macchine non deterministiche

Gli Automi e le Macchine di Turing descritte in precedenza erano deterministiche, ovvero fissato uno stato e un ingresso, la transazione è determinabile e calcolabile in modo univoco. Sono stati introdotti nella teoria anche delle varianti non deterministiche. Esse hanno funzioni di transizione da uno stato all'altro che non sono univoche, ovvero dato uno stato e un input è possibile avere più di una transizione verso altrettanti stati diversi.

Una stringa di ingresso in una macchina non deterministica è accettata se, almeno una delle possibili sequenze di transizioni conduce allo stato finale.

Algoritmi

Un algoritmo è una procedura per risolvere un problema, ed è una descrizione astratta di un programma per un calcolatore, ovvero una sequenza di istruzioni e/o operazioni che possono risolvere un problema. Tramite gli algoritmi si possono descrivere procedure che vengono poi tradotte in istruzioni analoghe nei vari linguaggi di programmazione. Per questo motivo, un algoritmo spesso non viene espresso in un linguaggio particolare, ma attraverso una descrizione delle operazioni da effettuare.

Un algoritmo deve avere le seguenti proprietà:

  1. Contiene una sequenza finita di istruzioni
  2. Ogni istruzione deve essere deterministica, ovvero eseguita in modo da produrre risultati precisi e prevedibili

Inoltre, essendo la descrizione della soluzione a livello astratto, si ipotizza di eseguire l'algoritmo in condizioni ideali, ovvero:

  1. La quantità di memoria disponibile sul dispositivo che esegue l'algoritmo non è limitata
  2. La dimensione delle stringhe di ingresso e di uscita non è limitata

Tesi di Church

Nella pratica i problemi sono risolti con algoritmi che non sono applicati per mezzo di macchine di Turing ma attraverso i linguaggi di programmazione. Tuttavia è possibile dimostrare che

Data una macchina di Turing M è possibile costruire un programma (in un qualunque linguaggio) che simuli M, purchè il calcolatore che effettivamente esegue il programma disponga di una quantità di memoria arbitrariamente grande. Dato un programma (in un qualunque linguaggio) è possibile costruire una macchina di Turing M che calcoli la stessa funzione calcolata dal programma.

Nella pratica, è accettabile che il calcolatore abbia memoria a sufficienza per memorizzare i relativi nastri di memoria e i dati di input e di output. Finché il calcolatore non esaurisce la memoria, essa si può considerare illimitata nei confronti della computazione che sta effettuando.

I linguaggi di programmazione non sono altro che un ulteriore formalismo di calcolo. Per la definizione formale di complessità si illustrano in genere teoremi ed enunciati che riguardano le macchine di Turing, tuttavia essi possono essere applicati ai programmi stesi in un comune linguaggio di programmazione.

La tesi di Church è di fondamentale importanza nella teoria della computazione, infatti essa afferma che:

  1. Non esiste alcun formalismo, per modellare una determinata computazione meccanica, che sia più potente delle macchine di Turing e dei formalismi ad esse equivalenti.
  2. Ogni algoritmo può essere codificato in termini di una macchina di Turing (o di un formalismo equivalente)

In pratica, se un problema non può essere risolto da una macchina di Turing, esso non può essere risolto da un qualunque altro modello matematico di calcolo o algoritmo.

Complessità

Con il termine di complessità si indica il costo necessario per risolvere un problema. Quest'ultimo può essere rappresentato dal tempo impiegato per la soluzione e/o dallo spazio di memoria richiesto. Infatti esistono alcuni problemi, detti intrattabili, che richiedono una quantità di tempo talmente elevata da renderli in pratica non risolvibili. E' possibile definire in modo formale la complessità di un problema, che riguarda il costo impiegato p er risolverlo tramite un algoritmo.

Un algoritmo riceve in ingresso una serie di dati di input e produce un certo output. La complessità dell'algoritmo spesso è funzione della quantità di dati in input. Si consideri il problema della ricerca di un elemento all'interno di un array di dimensione n. Un algoritmo di ricerca banale consiste nell'esaminare il contenuto di ogni locazione di memoria, partendo dalla prima, e confrontarlo con l'elemento cercato. Se si è fortunati, nel caso migliore, l'elemento cercato si troverà nella prima posizione, se si è sfortunati nell'ultima. Sia t il tempo impiegato dal computer su cui viene eseguito l'algoritmo per accedere alla locazione di memoria ed effettuare il confronto. Allora, nel caso migliore il tempo totale sarà Ttot = t, mentre nel caso peggiore sarà Ttot = nt.

In genere la complessità si misura utilizzando la dimensione temporale, perché è spesso l'aspetto più importante. Inoltre, la complessità dipende dall'algoritmo scelto per risolvere il problema. Indicare la complessità di un problema si utilizza la notazione detta theta-grande, che esprime a grandi linee come aumenta il costo di un algoritmo in funzione della dimensione dell'ingresso.

Infatti, per l'algoritmo di ricerca, nel caso peggiore il costo è proporzionale al numero di elementi, essendo nt. All'aumentare del numero di elementi dell'array il tempo necessario per trovare l'elemento desiderato è quindi direttamente proporzionale. In altre parole, raddoppiando il numero di elementi si raddoppia il tempo necessario per la ricerca.

Si è introdotta una notazione, detta notazione O-grande, che definisce asintoticamente l'andamento della funzione f(n) che indica il tempo necessario per risolvere un problema in funzione della lunghezza n dell'input.

Una funzione f(n) è O(g(n)) che si legge O-grande di g, se e solo se esistono due costanti positive c e n', tali che

(1)
\begin{align} \vert f(n) \vert < c g(n) \forall n' > n \end{align}

quindi, la funzione f(n) è inferiore alla funzione g(n), a meno di una costante c, per n sufficientemente grandi. Quindi è possibile che f(n) sia superiore a g(n) per n < n', tuttavia, per n che tende ad infinito prima o poi si manterrà inferiore a g(n). Per questo motivo la notazione descrive l'andamento asintotico. Si può inoltre osservare che, di conseguenza, la funzione f(n) non crescerà più di g(n). Quindi g(n) sarà un limite superiore.

Quando una funzione ha un andamento lineare si dice che è O(n), ovvero il tempo di esecuzione è direttamente proporzionale alla grandezza dell'ingresso. Quando invece una funzione è O(nk) si dice che ha andamento polinomiale. Infatti in questo caso la funzione f(n) che lega la grandezza dell'ingresso n al tempo di esecuzione è un polinomio del tipo $a_k n^k + a_{k-1} n^{k-1} + \dots + a_1 n + a_0$. Nel determinare l'andamento asintotico, si possono trascurare tutti i termini di grado inferiore a k poiché crescono con minore rapidità e considerare solo l'ordine maggiore, approssimando il polinomio con nk. Quindi la funzione è O(nk).

Una funzione ha un andamento esponenziale quando è di tipo O(kn), ovvero cresce in modo esponenziale, con k > 1.

Si supponga che un generico calcolatore compia un passo di un algoritmo in 1 us, ovvero effettui 1 milione di passi al secondo. Nella seguente tabella viene indicato il limite superiore di tempo necessario per risolvere un algoritmo, al variare della dimensione dell'ingresso e della complessità dell'algoritmo impiegato.

n \ O(n) O(logn) O(n) O(n logn) O(n2) O(2n)
10 1 us 10 us 10 us 100 us 1 ms
100 2 us 0.1 ms 2 ms 10 ms 1017 anni
1000 3 us 1 ms 3 ms 1 s
10000 4 us 10 ms 40 ms 100 s
1000000 6 us 1 s 6 s 11 giorni

Si può notare immediatamente che i tempi di esecuzione sono accettabili quando la complessità è O(logn), O(n), O(n logn), mentre diventano impegnativi per funzioni con complessità O(n2) e assolutamente proibitivi per le funzioni con complessità esponenziale. Per questo motivo gli algoritmi con complessità polinomiale sono detti trattabili, mentre quelli con complessità esponenziale o non polinomiale sono detti intrattabili, poiché all'aumento dei dati di ingresso il tempo impiegato per risolvere il problema diventa estremamente elevato.

Concetto di problema

Un problema astratto viene definito come una relazione binaria su un insieme di istanze del problema e l'insieme delle sue soluzioni. In altre parole, un problema può essere codificato come un insieme di valori di ingresso, appartenenti all'insieme delle istanze, che devono essere elaborati in qualche modo da un algoritmo per produrre un elemento appartenente all'insieme delle soluzioni.

Ad esempio, il problema della soluzione di una equazione di secondo grado ax2 + bx + c = 0 può essere pensato come una funzione il cui dominio è costituito dai tre valori a, b, c e la cui soluzione è una coppia di valori x1 e x2.

Le istanze di un problema sono i valori di un problema e costituiscono delle stringhe di un linguaggio. Possono essere codificate in vari modi, uno dei quali è il formato binario. In quest'ultimo, le stringhe sono formate da sequenze di 0 e 1, ovvero {0, 1}* e rappresentano una istanza del problema. Spesso si utilizza l'esempio seguente del problema del percorso minimo in un grafo: dato un grafo, che è definito univocamente dall'insieme dei suoi nodi V e dall'insieme degli archi E, ed avendo due nodi x e y, è possibile stabilire se tra essi esiste un percorso di costo (oppure peso o lunghezza) inferiore ad un dato k? Ogni arco del grafo è fornito di un valore associato che rappresenta il suo costo. I dati del problema, che rappresentano una sua istanza, sono costituiti dagli insiemi V, E, dai nodi x e y e dalla costante k. Se esiste un tale percorso, la soluzione del problema è codificata come il sottoinsieme di nodi ed archi da attraversare per poter collegare i nodi x e y.

Problema di riconoscimento

Si dice che un algoritmo A riconosce un linguaggio se produce il valore 1 per ogni stringa appartenente ad esso. In altre parole, data una stringa i e un linguaggio L si ha

(2)
\begin{align} A(i) = 1 \mbox{ se } I \in L \end{align}

Nel problema del percorso minimo in un grafo (che si indicherà con G ed è costituito dagli insiemi dei nodi V e degli archi E), la stringa di input i è costituita dai valori di un dato grafo G, di due suoi nodi x e y di partenza e di destinazione e di una lunghezza massima k. Se esiste un percorso con lunghezza inferiore a k, allora l'algoritmo fornisce il valore 1. Il linguaggio L può essere definito come l'insieme dei percorsi con lunghezza inferiore a k esistenti tra x e y in un grafo G, ovvero l'insieme delle soluzioni.

Problema di decisione

Il problema di decisione è una versione più ristretta rispetto a quello di riconoscimento, infatti si dice che un algoritmo A decide un linguaggio L se produce il valore 1 per ogni stringa che appartiene al linguaggio e il valore 0 per ogni stringa che non appartiene ad esso. Quindi, data una stringa i e un linguaggio L si ha:

(3)
\begin{align} A(i)=1 \mbox{ se } I \in L \end{align}
(4)
\begin{align} A(i)=0 \mbox{ se } I \notin L \end{align}

In comparazione, una stringa appartenente al linguaggio L produce il valore 1 sia da un algoritmo di riconoscimento che da un algoritmo di decisione, ma solo un algoritmo di decisione riesce a stabilire se una stringa non appartiene al linguaggio, perché non è garantito che l'algoritmo di riconoscimento non riconosca anche qualche stringa che non appartiene ad esso.

Problema di verifica

Si dice che un algoritmo A verifica un linguaggio L se data una stringa i di input e una stringa j detta certificato, allora

(5)
\begin{equation} A(i, j) = 1 \end{equation}

dove il certificato j serve per dimostrare che i appartiene ad L. Per ogni stringa i non in L non esistono certificati che dimostrino che x è in L.

Nel problema del percorso minimo in un grafo, la stringa di input i è costituita dal grafo G, dai nodi x e y e dalla costante k che indica la lunghezza massima. Il certificato j, ovvero una soluzione, è costituito invece da un percorso attraverso il grafo che parte da x e raggiunge y. Il certificato dimostra quindi che nel grafo G è presente un percorso che conduce da x a y in una lunghezza inferiore a k, ovvero che l'input i appartiene al linguaggio delle soluzioni L. La verifica consiste banalmente nel calcolare la somma delle lunghezze del percorso indicato nel certificato e di conseguenza dimostrare che il grafo G possiede un tale percorso da x a y.

Classi di complessità P e NP

Si dice che un linguaggio L è riconosciuto da un algoritmo A in tempo polinomiale se per qualunque stringa $i \in L$ di lunghezza n, si ha A(i) = 1 in un tempo O(nk), con k costante.

Si dice che un linguaggio L è deciso da un algoritmo A in tempo polinomiale se per qualunque stringa i di lunghezza n, si ha A(i) = 1 se e solo se $i \in L$ e A(i) = 0 se e solo se $I \notin L$ in tempo O(nk), con k costante.

P è la classe dei linguaggi che possono essere riconosciuti mediante un algoritmo di tempo polinomiale, ovvero

(6)
\begin{align} P = \lbrace L : L \mbox{ riconosciuto in } O(n^k) \rbrace \end{align}

La classe di complessità NP è la classe di linguaggi che possono essere verificati mediante un algoritmo di tempo polinomiale. Un linguaggio L appartiene a NP se e solo se esiste un algoritmo A di tempo polinomiale tale che

(7)
\begin{align} L = \lbrace i= \lbrace 0, 1 \rbrace *: \mbox{ esiste j tale che } A(i, j) = 1 \rbrace \end{align}

Si dice che l'algoritmo A verifica il linguaggio L in tempo polinomiale.

Riassumendo, dato un problema i suoi dati sono pensabili come una stringa di valori. In un problema appartenente alla classe di complessità P, è possibile decidere in un tempo polinomiale se questa stringa appartiene ad un linguaggio L che contiene l'insieme delle istanze dei problemi che hanno soluzione. Invece, in un problema appartenente alla classe di complessità NP, data una istanza di input con i valori del problema e una soluzione, è possibile verificare questa soluzione in tempo polinomiale, permettendo di stabilire che l'istanza in input appartiene al linguaggio L.

Originalmente veniva fornita una definizione alternativa per la classe NP, ovvero come quell'insieme dei linguaggi che possono essere riconosciuti in tempo polinomiale da una macchina di Turing non deterministica. Data una funzione f, si possono introdurre le seguenti classi di linguaggi:

  • DTIME: insieme dei linguaggi L riconosciuti da qualche MT deterministica con complessità di tempo $T \leq f$
  • DSPACE: insieme dei linguaggi L riconosciuti da qualche MT deterministica con complessità di spazio $S \leq f$
  • NTIME: insieme dei linguaggi L riconosciuti da qualche MT non deterministica con complessità di tempo $T \leq f$
  • NSPACE: insieme dei linguaggi L risconosciuti da qualche MT non deterministica con complessità di spazio $S \leq f$

Da questi insiemi si definiscono alternativamente le classi di complessità P e NP in questo modo:

(8)
\begin{align} P = \mbox{ unione di tutti i linguaggi } DTIME(n^i) = DTIME(n) \cup DTIME(n^2) \cup DTIME(n^3) \cup \dots \end{align}
(9)
\begin{align} NP= \mbox{ unione di tutti i linguaggi } NTIME(n^i) = NTIME(n) \cup NTIME(n^2) \cup NTIME(n^3) \cup \dots \end{align}

Mentre la definizione della classe P è analoga a quella precedente, per la classe NP viene utilizzato il concetto di macchina di Turing non deterministica.

Riducibilità

Dati due linguaggi L1 e L2, se esiste una funzione calcolabile in tempo polinomiale f tale che per ogni stringa x

(10)
\begin{align} x \in L1 \mbox{ se e solo se } f(x) \in L2 \end{align}

allora si dice che L1 è riducibile a L2 ed si indica con la notazione $L1 \leq_p L2$. Considerando due problemi P1 e P2, che corrispondono ai due linguaggi L1 e L2, una istanza x di P1 può essere trasformata attraverso la funzione f in una istanza f(x) di P2. Se f(x) è una soluzione di P2, allora x è una soluzione di P1. I due problemi, e dunque i due linguaggi, sono correlati da una funzione polinomiale.

Se L1 ed L2 sono legati da questa riducibilità, allora la complessità di risoluzione di L2 è elevata almeno quanto L1, a meno di un fattore polinomiale. Quindi, se L2 appartiene alla classe di complessità P, allora anche L1 appartiene alla classe di complessità P. Inoltre, se L1 appartiene alla classe di complessità NP allora anche L2 appartiene a questa classe.

Difficoltà e completezza

Sia L una classe di linguaggi. Un linguaggio l si dice L-difficile (o L-arduo, dall'inglese L-Hard) rispetto alle riduzioni in tempo polinomiale se e solo se, per ogni h appartenente a L, h è riducibile in tempo polinomiale a l, ovvero

(11)
\begin{align} h \leq_p l \mbox{ con } h \in L \end{align}

Un linguaggio L-difficile è quindi difficile da risolvere almeno quanto ogni linguaggio di L. Data una classe L di linguaggi, un linguaggio l si dice L-completo se e solo se è L-difficile ed appartiene ad L.

In base a queste definizioni, si possono introdurre le classi di complessità NP-difficile e NP-completa. Quest'ultima è particolarmente importante, poiché contiene tutti i problemi in NP che sono difficili almeno quanto ogni altro problema NP. Quindi, nessun altro problema NP ha complessità maggiore a meno di un fattore polinomiale. Nell'ambito dell'informatica esistono molti problemi NP-completi che sono di grande interesse pratico. La loro soluzione esatta tuttavia non è calcolabile in casi pratici a causa della complessità degli algoritmi impiegati per risolverli. E' dunque enorme l'interesse nel trovare un algoritmo in P che possa risolvere questi problemi. Si può dimostrare che, se un problema NP-completo può essere risolto esattamente in tempo polinomiale, allora ogni altro problema NP-completo può essere risolto in tempo polinomiale.

In altre parole, in questo caso le classi di complessità P ed NP coinciderebbero, ovvero si avrebbe P = NP. Se si dimostrasse invece che non esiste alcun algoritmo polinomiale in grado di risolvere uno dei problemi NP-completi, allora nessun altro problema potrebbe essere risolto in tempo polinomiale.

Attualmente nessuna delle due ipotesi è stata dimostrata, e la questione se P = NP rimane uno dei problemi aperti più importanti1 nella matematica e sicuramente il più importante nell'ambito dell'informatica teorica.

Problemi NP-Completi

I seguenti sono alcuni tra i classici problemi NP-completi, anche se ne sono stati scoperti molti altri.
Soddisfacibilità delle formule (SAT) : Data una formula W con variabili X1 , X2 , …, Xn , esistono n valori delle variabili tali che W sia vera?
Cicli Hamiltoniani (HC): Dato un grafo G, esiste un percorso che visita ogni nodo del grafo esattamente una volta tornando al vertice di partenza?
Commesso viaggiatore (TSP): Dato un grafo G i cui archi hanno associato un costo, esiste un percorso che visita ogni nodo del grafo esattamente una volta, tornando al punto di partenza e il cui costo è minimo?
Clique (CP): Dato un grafo G, esiste un sottografo tale che ogni coppia di nodi sia collegata da un arco e il numero di nodi di questo sottografo è massimo?

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License