Nei precedenti capitoli di questa serie ci siamo soffermati sullo studio degli algoritmi risolutivi, spostiamo ora l’attenzione sullo studio dei problemi. In particolare soffermiamoci sulla possibilit√† di classificare questi ultimi sulla base delle risorse utili a ottenere una soluzione.

Per prima cosa raggruppiamo grossolanamente i problemi in tre classi:

  1. Problemi che ammettono algoritmi di soluzione efficiente;
  2. Problemi che non ammettono risoluzione mediante algoritmi efficienti e che per questo vengono definiti intrattabili;
  3. Problemi per i quali non sono ancora stati definiti algoritmi di risoluzione efficienti, ma per i quali nessuno ha ancora dimostrato che essi non esistano.

Molti problemi di notevole interesse appartengono al terzo gruppo.