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 polinomiali non deterministici (NP)
Insiemisticamente, P ( NP ( EXP

Osserva

  • si sceglie uno di questi problemi, per esempio il commesso viaggiatore, e si dichiara NP Completo, NP-C
  • dato un problema NP si possono trasformare i suoi dati input e output e utilizzare l’algoritmo risolutivo di un altro problema NP-C già noto
  • se dovesse esistere un algoritmo polinomiale per un qualsiasi problema NP-C potrebbe essere utilizzato per tutti gli NP-C…

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.