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.
Iscriviti a:
Commenti sul post (Atom)
Post
NEL PDF DI:
RispondiEliminaing. Rosario Turco, prof. Maria Colonnese
Proposta di dimostrazione
alle
Ipotesi di Riemann e
Congettura molteplicità degli zeri
QUESTO PASSO
...
La convergenza a zero delle due serie, comporta che i due valori s e 1-s , al tendere di n
all infinito, si incontrano a 1/2 quindi, la convergenza avviene sulla retta criticaa =1/2. Ora poichè
l annullamento di u e v individua gli zeri non banali, siamo arrivati alla conclusione che gli zeri non
banali stanno sulla retta critica a =1/2.
...
PURTROPPO QUESTO PASSAGGIO NON PORTA ALLA DIMOSTRAZIONE.
szanotti@libero.it