Il 11/04/11 22.56, Giorgio Pastore ha scritto:
>
> V vol. (Fisica Statistica) ,
> capitolo XIV paragrafo 151 (almeno sulla traduzione italiana degli
> editori riuniti).
>
Grazie mille, mi sa che non l'avrei mai trovato "infilato li in mezzo"! ;-)
Nel frattempo ho poi chiesto al docente, che mi ha dato due articoli che
ho poi visto essere questi (il primo e' in pratica un abstract del secondo):
Barry Cipra, MATHEMATICS: Statistical Physicists Phase Out a Dream,
Science , vol. 288, pp. 5471, June 2, 2000
S. Istrail, Statistical Mechanics, Three-Dimensionality and
NP-Completeness: I. Universality of Intractability of the Partition
Functions of the Ising Model Across Non-Planar Lattices, Proceedings of
the 32nd ACM Symposium on the Theory of Computing (STOC00), ACM Press,
p. 87-96, Portland, Oregon, May 21-23, 2000
PDF scaricabili da:
http://www.cs.brown.edu/~sorin/ising.htm
La sostanza direi essere che Sorin Istrail ha dimostrato che il trattare
un modello di Ising per D>2 e' un problema NP-completo, e quindi
"equivalente" a tutti gli altri problemi NP-completi in circolazione.
La soluzione analitica del modello di Ising per D>2 vorrebbe quindi dire
trovare una soluzione quantomeno computazionalmente trattabile per molti
algoritmi che fino ad adesso hanno "resistito".
Quindi la portata e' grande: non "possiamo" piu' parlare di soluzione di
un singolo problema a se stante, ma dobbiamo considerare l'eventuale
soluzione "di ising" la soluzione di un'intera classe di problemi:
problemi per i quali fin'ora non e' stato trovato neanche un algoritmo
computazionalmente trattabile....
Ovviamente non impossibile, ma..... :-)
(...inoltre sospetto che sperare in una soluzione analitica sia ancora
piu' forte che sperare in un algoritmo di risoluzione computazionalmente
trattabile.... ma qua ci vorrebbe qualche matematico informatico.... ;-) )
Questo almeno e' quello che ho capito io.
> Giorgio
Ciao
Andrea Barontini
Received on Sat Apr 16 2011 - 10:05:43 CEST