Complessità: problemi difficili

L’argomento viene trattato in modo molto semplificato.

Definiamo polinomiali quei problemi con

T(n) <= nc, (c > 1)

e esponenziali quelli con

T(n) <= an, (a > 1).

Esistono molti problemi che ammettono un algoritmo risolutivo esponenziale ma per i quali non si è certi che la loro complessità sia esponenziale e si spera che in futuro possano essere ricondotti nella classe dei polinomiali.

Si definiscono problemi non polinomiali (NP), insiemisticamente: P ( NP ( EXP

Tra questi problemi (commesso viaggiatore, zaino, …) esiste una relazione sorprendente: sono tutti equivalenti tra loro!

Ogni volta che è stato introdotto un nuovo problema tra gli NP è stato dimostrato che, a meno di qualche adattamento, la sua soluzione può essere ricavata a partire dalle soluzioni di un altro problema già noto come NP.

Se dovesse esistere un algoritmo polinomiale per uno qualsiasi tra essi questo potrebbe essere utilizzato anche per tutti gli altri.

Problemi intrattabili

Ci sono problemi per i quali si può dimostrare che il tempo di esecuzione del miglior algoritmo è almeno esponenziale

  • torre di Hanoi
  • permutazioni

Si dice che sono problemi intrinsecamente esponenziali.
Sono problemi intrattabili per la maggior parte delle loro istanze.

Notice: This work is licensed under a BY-NC-SA. Permalink: Complessità: problemi difficili

Comments are closed.