Per formalizzare qualcosa di complicato si comincia dalle cose più semplici. Per la teoria della complessità si comincia dai problemi decisionali. Questi hanno una formulazione più semplice rispetto ad un problema generico.
Dobbiamo andare a capire quanto siano efficienti per le soluzioni a questi problemi. La classe più bella si chiama classe P: problemi decisionali per cui esiste un algoritmo risolutivo di tempo polinomiale. Come si fa a far vedere l’appartenenza a questa classe? Faccio vedere che c’è un algoritmo di costo polinomiale che risolve il problema.
Intanto cerchiamo di capire e facciamo un esempio per vedere qualche che sia uno dei problemi decisionali difficili per cui non possiamo assumere veramente nulla.
Problema del ciclo hamiltoniano: prendiamo un grafo connesso qualunque. Esiste un ciclo che passa per tutti i nodi una volta sola? Si, ma non è facile trovarlo per un grafo qualunque in tempo polinomiale, ma non è nemmeno stato dimostrato il contrario! Che me ne faccio di questi problemi di classe P, che non sono ne’ carne né pesce praticamente.
Come posso caratterizzarli? Se ci pensiamo questo problema ha una caratteristica particolare. Non so trovare il ciclo, ma se qualcuno trova un ciclo te sai in grado di dire che questo sia un ciclo hamiltoniano oppure no? Se ti do una permutazione di nodi in modo da simulare un percorso, riesci a capire se è vero oppure no.
Possiamo quindi fare questo tipo di verifica, quindi non ho un problema con risoluzione polinomiale, ma posso provare a dedurli in un certo senso. Non è così bello come avere la soluzione, ma è interessante che si riesca a fare la verifica in tempo polinomiale. Ovviamente è più debole come verifica.
Questa idea di poter verificare si formalizza come concetto di certificato. Quando abbiamo un problema di tipo decisionale questi associa una istanza ad un output. In questo caso ho un output che è solamente si o no.
Un certificato per una istanza positiva è una evidenza che quell’istanza sia positiva: è una sequenza di caratteri con l’evidenza che quell’istanza sia positiva.
Ci interessa che il certificato abbia una dimensione polinomiale per fare una verifica di tempo polinomiale. Altrimenti pago esponenziale, o altri valori per fare la verifica e non è interessante. Ci serve anche un algoritmo verificatore, che si prende l’istanza il certificato e risponde Si oppure No in base all’istanza che viene dato in pasto.
Quando voglio verificare un problema voglio andare a fare vedere che sono in grado di avere un certificato di dimensione polinomiale e avere un algoritmo verificatore che dice si per istanza positiva e certificato valido.
Adesso posso andare a definire la classe di NP, cioè tutti i problemi che riesco a verificare in tempo NP. P ed NP non vuol non polinomiale perché in questa definizione è più facile da capire e digerire rispetto all’utilizzo della macchina di Turing.
NP Problemi sono quelli verificati da una macchina di turing non deterministica in tempo polinomiale.
A questo punto ci si chiede in che relazione stanno queste due classi. Verificare è più semplice. Quando risolvo posso verificare, mentre non è vero il contrario.
Certificato è una sequenza vuota per i problemi P, perché con un verificatore che devo far un test con un algoritmo stesso che se funziona praticamente un certificato di questo tipo va bene. Questa cosa me la devo rivedere
Al momento nessuno è riuscito a dimostrare che le due cose P e NP sono diverse e sono uguali e sono decenni che ci portiamo avanti questa incertezza e abbiamo una teoria che portiamo avanti con P e NP e tutte le ipotesi delle loro relazioni.
Gli scenari possibili al momento sono:
Si vede che problemi che riesco a verificare che sono i più difficili di quelli che riesco a risolvere in tempo polinomiale. Questi problemi sono NP completi. Questi sono molto importanti per vari motivi. Perché qui ci sono dentro un sacco di problemi e non sono solo problemi che possiamo trascurare come irrisolvibili, intrattabili, artificiosi. Questi saltano fuori praticamente ovunque e devo capire che proprietà hanno. Questi sono tutti quanti equivalentemente difficili. Se dimostro che uno solo è risolvibili allora così anche tutti gli altri.
Ogni problema nuovo che finisce lì dentro è un candidato in più per andare a risolvere la situazione. Fino ad una dimostrazione non possiamo dire nulla. Ovviamente la comunità scientifica tifa per la questione degli algoritmi P≠NP.