Complessità computazionale

Si cerca di catalogare dal punto di vista computazionale i problemi intrattabili, ovvero problemi risolvibili ma non in modo efficiente (ovvero in tempo polinomiale). In alcuni casi si pensa che non esista una soluzione ma non si hanno dimostrazioni in merito, mentre in altri casi è addirittura dimostrato. Abbiamo quindi delle categorie informali per i problemi:

• Facili (o trattabil): so risolverli in modo efficiente.

• Difficili, o più formalmente, intrattabili: so risolverli ma non in modo efficiente e non ho una dimostrazione che mi assicuri che non siano risolvibili in modo efficiente.

  • Difficilissimi: (probabilmente intrattabili) se riuscissi a risolvere con algoritmi efficienti → tutti i difficili sarebbero facili.

  Esistono anche problemi forse intrattabili.

• Dimostrabilmente difficili: risolvibili con algoritmo non efficiente e posso dimostrare che non esiste un algoritmo efficiente. Sono poco interessanti.

• impossibili (o indecidibili): posso dimostrare che non esiste un algoritmo che li risolve (indipendentemente dalle risorse computazionali)

Andiamo a definire alcuni concetti che utilizzeremo:

Definizione: Problema Computazionale: è composto da un input, da un output, e dalla relazione che c’è tra di essi.

• Input: come sono fatti i dati
• output: come sono fatti i risultati

Esempio classico: problema dell’ordinamento

Definizione: Algoritmo: Una procedura composta da un numero finito di operazioni concrete e generali tale che se applicata a un’istanza, calcola un output corretto del problema in un tempo finito (per tutte le possibili istanze).

Problema: Arco Minimo

Problema: Raggiungibilità

Problema: TSP (Travelling Salesman Problem)

Classificazione degli algoritmi

Definiamo un algoritmo come una sequenza di istruzioni elementari (supportate dal calcolatore) che, eseguite in sequenza, mi portano alla soluzione di un problema. Si ha quindi che un algoritmo $A$ risolve un problema $\Pi$ se per ogni possibile istanza di $\Pi$ l’algoritmo $A$ mi da la risposta corretta.

Distinguiamo però:

• algoritmo efficiente: da la soluzione in tempo polinomiale rispetto alla dimensione dell’input. Ho una crescita di tempo accettabile all’aumentare dell’input.
• algoritmo non efficiente: da la soluzione ma in tempo superiore a quello polinomiale. Ho un caso peggiore limitato superiormente da un esponenziale: $O(2^n)$. Ho una crescita di tempo assolutamente non accettabile (espnenziale, appunto) all’aumentare dell’input.