Uno dei problemi del millennio è, come abbiamo visto anche in blog precedenti, P=NP? Ci si chiede cioè, di fronte a problemi decisionali tipicamente NP, non risolvibili con algoritmi polinomiali (P) essendo per natura essi esponenziali con l'input come il problema dello zaino e tanti altri, se è possibile individuare degli algoritmi polinomiali (deterministici o non ) tali che si possa poi affermare, invece, che P=NP. Cook e Levin aprirono la strada col loro Teorema su queste tematiche ed una delle loro dimostrazioni riguardava i problemi SAT, cioè i problemi di "Soddisfacibilità booleana" (SAT) costituiti da AND di clausole, dove ogni clausola è un OR di letterali. Ad esempio il 2SAT ha un OR con 2 letterali e il 3SAT un OR con tre letterali.
Per il 3SAT, ad esempio, il problema è di:
1) verificare se esiste una soluzione TRUE per la funzione logica assegnata
2) se la funzione logica esaminata è minimizzabile
3) elencare le soluzioni delle funzione logica assegnata
La sfida è di trovare, per fare questo, un algoritmo polinomiale. Un articolo su questo è su www.scribd.com/rosario_turco
Provate a scrivere un algoritmo in PARI/GP e poi fatemi sapere ... Soprattutto considerate cosa succede all'aumentare del numero di letterali e la velocità del vostro algoritmo.
Post
