Complessità: problemi difficili

di

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).

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.

Problemi NP

Esistono molti problemi che hanno tutti le stesse caratteristiche

  1. data una potenziale soluzione è possibile verificare in tempo polinomiale la sua correttezza
  2. ammettono un algoritmo polinomiale ma con una macchina non deterministica
  3. non è dimostrato che la complessità del problema sia esponenziale

Si definiscono problemi polinomiali non deterministici (NP).
Insiemisticamente, P ( NP ( EXP.

Problemi NP-C

Osserva

  • Si sceglie uno dei problemi NP, per esempio il problema del commesso viaggiatore, e si dichiara NP Completo, NP-C.
  • STRANO… tutti i problemi NP studiati sono riconducibili al problema NP-C fissato, basta manipolare i dati in ingresso e in uscita.
  • CONCLUSIONE: se dovesse esistere un algoritmo polinomiale per uno qualsiasi dei problemi NP-C potrebbe essere utilizzato per risolvere tutti i problemi NP-C.
  • P = NP ???

Nel frattempo la ricerca va avanti… esistono algoritmi che non possono promettere di dare la risposta ottima ma ci offrono quasi sempre una risposta quasi ottima.