Download

Pagina 3SAT by Luigi Salemi


In figura il confronto tra 2 algoritmi che lavorano in tempo O(2n) e O(n9) rispetto al n. delle Variabili ipotizzando che entrambi siano capaci di esaminare 1.000.000 di casi al secondo. Per motivi evidenti i tempi sono riportati in scala logaritmica.

Se siete arrivati qui probabilmente sapete già la differenza tra la classe dei problemi "P" e "NP", se vi siete persi e mi avete raggiunto per errore vi dico che nella classe P sono contenuti i problemi per i quali si conosce un algoritmo che li risolve in tempo Polinomiale, mentre nella classe NP sono contenuti i problemi per i quali si conosce solo un algoritmo di risoluzione in tempo Esponenziale (ma beffardamente l'algoritmo di verifica lavora in tempo Polinomiale). Il grafico chiarisce in modo immediato quanto grande sia la differenza, in relazione ai tempi, tra le 2 tipologie di algoritmi.

Ciò che il grafico non dice è che i problemi più interessanti (es.: quello del commesso viaggiatore o dei percorsi minimi, quello dello zaino o sub somma, la scomposizione in fattori primi [su cui si basa quasi tutta la crittografia esistente]) sono nella classe NP. La buona notizia e che ogni tanto un problema da NP si trasferisce in P perché si trova un algoritmo più efficiente che lavora in tempo Polinomiale, e questo il caso della "verifica di primarità" che nel 2002 si è trasferito in P per merito di 3 matematici indiani Manindra Agrawal, Neeraj Kayal e Nitin Saxena. 

Da un bel po' di anni si cerca di provare se le classi P e NP siano effettivamente distinte (ovvero esiste almeno un problema in NP che mai si potrà trasferire in P) o se viceversa le 2 classi in realtà coincidono, ma noi non siamo stati ancora capaci di trovare l'algoritmo unificatore, quello per cui ogni problema di NP si possa risolvere in tempo Polinomiale

Leonid Levin e Stephen Cook hanno scoperto separatamente, all'inizio degli anni '70, che tutti i problemi della classe NP si possono ricondurre ad un unico problema denominato "SAT" in cui occorre risolvere una espressione booleana trovando, se esiste, una n-upla di valori True/False che soddisfi la espressione. Come dire risolto SAT risolti tutti, peccato che anche SAT sia un problema della classe NP.

Subito dopo si è visto che SAT si può ricondurre a "3SAT", un problema in cui bisogna trovare, se esiste, la soluzione di una espressione booleana che è formata dalla congiunzione di Clausole; ogni Clausola essendo composta dalla disgiunzione di esattamente 3 (da cui il nome 3SAT) Variabili booleane eventualmente negate. Es: (A1 or ~A2 or A3) and (~A1 or ~A3 or A4) and ..

Pensavo di aver trovato un Metodo che risolvesse ogni problema 3SAT in tempo polinomiale, poi mi sono accorto che ero in errore perché ho trovato un contro esempio.

Pazienza, continuo a lavorarci. Luigi Salemi