Tutti abbiamo la nozione, seppure sommaria, di soluzione di un problema. Questo concetto normalmente viene associato con tecniche deterministiche, ovvero procedure in grado di realizzare un'analisi del problema e fornire la soluzione in tempo finito. Tuttavia, esiste il fatto che solo i problemi trattabili in tempo polinomiale sono analizzabili in questo modo per cui molti problemi, soprattutto quelli riguardanti ricerche di ottimo, non sono suscettibili di trattamenti di questo genere. Dalla parte dei problemi non trattabili in tempo polinomiale abbiamo ad esempio la maggior parte dei problemi di ottimo e i problemi che dipendono da vettori dei parametri di grandi dimensioni. L'esempio più noto di questo tipo di problemi è probabilmente quello del "commesso viaggiatore". Questo problema non è trattabile in tempo polinomiale; l'unica cosa che si può fare è capire, in tempo polinomiale, se date due proposte di soluzione che soddisfano i vincoli del problema una è migliore o peggiore dell'altra.

La non polinomialità per quanto riguarda la risoluzione di un problema obbliga l'utilizzo di tecniche approssimate. Allo scopo di chiarire la necessità di mutare la visione dei problemi che devono essere trattati con tali tecniche (obbligando a parlare non più di "soluzioni" ma di "soluzioni soddisfacenti"), possiamo strutturare il nostro ragionamento nei seguenti punti:

• Dal punto di vista della complessità i problemi non sono tutti uguali. Si possono classificare in problemi risolvibili in tempo polinomiale e in tempo superpolinomiale.
• Dal punto di vista della trattabilità, si considera che solo i problemi per i quali c'è un algoritmo di risoluzione in tempo polinomiale sono trattabili. I problemi superpolinomiali sono considerati intrattabili. I problemi intrattabili richiedono lo sviluppo di tecniche di risoluzione approssimate.
• I problemi che consentono una verifica di una data proposta di soluzione per un problema in tempo polinomiale si dicono problemi NP. Con tutta probabilità, la classe P è un sottoinsieme della classe NP; cioè, il numero di problemi risolvibili in tempo polinomiali è minore del numero di problemi verificabili in tempo polinomiale. All'interno della classe NP c'è una ulteriore classe di complessità, diversa dalla P, chiamata NPC che comprende i problemi NP completi, che possono essere considerati i problemi più ardui di NP.
• I problemi NPC sono considerati intrattabili (non risolvibili in maniera esatta in tempo polinomiale); possono essere abbordati solo in maniera approssimata. Inoltre, hanno la caratteristica che se solo uno potesse essere risolto in tempo polinomiale, usando il concetto di riducibilità, tutti i problemi della classe NP potrebbero essere risolti anch'essi in tempo polinomiale, dando come risultato che le classi NP e P sarebbero la stessa, conclusione che si considera molto improbabile nell'attualità.
• La verificabilità è il concetto chiave. La cosa importante è che benché si abbia a che fare con un problema enormemente complesso, come un problema NPC, date due proposte di soluzioni accettabili che soddisfino i vincoli del problema, si può verificare in tempo polinomiale quale delle due fornisce il migliore risultato.

Quest'ultimo punto è di importanza fondamentale. Se abbiamo tra le mani un problema enormemente complesso dobbiamo risolverlo in maniera approssimata per le ragioni esposte di seguito: se il problema fosse NP si potrebbe pensare di generare tutte le soluzioni possibili e usare la verificabilità in tempo polinomiale per tenerci la miglior soluzione trovata a un certo momento. Il punto però è che se, ad esempio, il problema è risolvibile in tempo superpolinomiale, possiamo non riuscire a generare tutte le soluzioni possibili in un tempo ragionevole. L'analisi di tutte le possibili soluzioni è sinonimo di risoluzione esatta del problema, per cui l'impossibilità di fare ciò ci costringe a costruire procedure approssimate.

A questo punto vale la pena di farsi la seguente domanda: in quale modo possiamo riuscire, tramite una tecnica approssimata, ad avvicinarci a una buona soluzione per i problemi del tipo discussi nel paragrafo precedente? È chiaro che se solo possiamo studiare una parte di tutte le possibili soluzioni dobbiamo restringere lo spazio di ricerca, ma questa restrizione deve essere fatta con criterio, altrimenti si rischia di lasciare da parte porzioni dello spazio delle soluzioni potenzialmente ottime.

Le tecniche evoluzionistiche sono un modo di realizzare tutto questo. In pratica, forniscono un criterio per esplorare solo alcune parti dello spazio delle soluzioni per il problema, facendo in modo di ridurre al minimo la probabilità che le porzioni non esplorate contengano soluzioni ottimali. L'unico vincolo è che il problema appartenga alla classe NP, cioè, che data una proposta di soluzione questa possa essere verificata in tempo polinomiale.

Quanto detto è sufficiente per evidenziare una caratteristica fondamentale dei problemi NP in generale, che consiste nella impossibilità di sapere, dal momento che vengono trattati in genere con metodi approssimati, se a un dato momento si sia arrivati o meno all'ottimo del problema o quanto lontano si sia da esso. Questo punto muta radicalmente la nozione di soluzione di un problema: adesso è solo possibile raggiungere delle soluzioni approssimate o soddisfacenti, essendo impossibile capire la bontà relativa di questa soluzione rispetto all'ipotetico ottimo globale del problema.

La similitudine con meccanismi tratti del mondo reale è in realtà molto ricca e fornisce spunti per altri algoritmi oltre quelli evoluzionistici. Tra questi ci sono le analogie col mondo fisico come il simulated annealing proposto da Kirkpatrick che consente di risolvere problemi su vasti spazi di ricerca usando relazioni del tipo della funzione di probabilità di Boltzmann, che nel processo fisico di raffreddamento di un solido quantifica la quantità di particelle che a una data temperatura hanno energia compressa tra  E  e  E + dE , per quantificare la probabilità che un punto dello spazio debba essere accettato come ottimo del problema o meno. A questo proposito viene definita una temperatura  T, concetto simile a quello di temperatura fisica di un solido che si raffredda progressivamente, che è in relazione con lo stato energetico del problema a un dato punto del calcolo. La funzione di distribuzione, insieme al criterio di Metropolis, forniscono una condizione per il movimento attraverso lo spazio del problema che si vuole esplorare.