Notícia antiga mas importante
Acho muito curioso que vérios sitemas em física estatística são insolúveis em d = 3. Por que exatamente nesta dimensão? Por que não em d = 4, d = 11, ou d = 32? . Seria uma coincidência que também d = 3 é a dimensão espacial de nosso universo? Ou estariam as duas coisas relacionadas? Por exemplo, talvez o fato de que um modelo físico seja NP-completo seja um pré-requisito para ele representar sistemas complexos de uma hierarquia superior. Ou, invertendo as coisas, só é possivel ter verdadeira complexidade (seja isso o que for) na presença de problemas NP-completos, e isso, em termos de sistemas físicos, ocorre geralmente com d = 3. Mais um argumento a là princípio antrópico fraco para o fato de que d = 3 em nosso universo. O outro argumento, se bem me lembro, se relacionava com a questão da estabilidade de órbitas keplerianas em d dimensões...
Sandia researcher Sorin Istrail (Photo by Randy Montoya)
Three-dimensional proof for Ising model impossible, Sandia researcher claims to have shown
Why, in Superbowl of statistical mechanics, famous players could never cross goal line
By Neal Singer
When a lake freezes over, how do trillions of randomly oriented water molecules know at almost the same time to align themselves into crystalline form? Similarly, when iron becomes magnetized, how do trillions of atoms know to align their spins almost instantly?
The best-studied model in science to discuss these phase changes and, indeed, a wide variety of changes in state (neural networking, protein folding, flocking birds, beating heart cells, questions of economics, and more) is the Ising model, developed by Ernst Ising in 1926 as part of his PhD dissertation.
Ising conceived of a linear chain, composed of particles that have magnetic moments called ³spins² able to take an up or down position. Each particle¹s spin influences the spins of the moments bordering it. The conception was expanded almost 20 years later into a two-dimensional grid of upward or downward spins, each spin influencing the behavior of spins around it, with a wider application in the material world.
The model can be expanded to any three-dimensional lattice model, and its properties figured out numerically with a high degree of accuracy. But not exactly. Not for the general case. As opposed to the known mathematical solutions for one or two dimensions, no one has been able to find an exact solution to any three-dimensional lattice problem in terms of elementary equations you could look up in a math book.
The continued application of Ising¹s model ‹ more than 8,000 papers published between 1969 to 1997 ‹ has tempted many scientists to extend the grid¹s usefulness into three dimensions, the realm in which most real-world problems take place.
Now Sandia computational biologist Sorin Istrail has shown that the solution of Ising¹s model cannot be extended into three dimensions for any lattice, and so exact solutions can never be found.
Sorin, who has just taken entrepreneurial leave from Sandia to accept the position of Senior Director of Informatics Research with Celera Genomics Corporation, says his paper will be published in May in the Proceedings of the Association for Computing Machinery¹s (ACM) 2000 Symposium on the Theory of Computing.
Says Sorin, ³Naturally, it¹s not as useful as finding the Holy Grail. We all wanna be like Lars [Onsager, the Nobel-Prize chemist who, in a mathematical tour-de-force, extended the Ising model solution from one dimension to two]. But at least no one now needs to spend time trying to solve the unsolvable.²
To prove that the solution could not be extended, Sorin resorted to a method called computational intractability, which identifies problems that cannot be solved in humanly feasible time. There are approximately 6,000 such problems known in all areas of science. They are all mathematically equivalent to each other. A solution to one would be a solution to all. Says Sorin, ³I showed that the Ising problem, for any lattice, is one of those problems. Therefore, it is computationally intractable.²
Nobel laureate Richard Feynman wrote in 1972 of the three-dimensional Ising model that ³the exact solution for three dimensions has not yet been found.²
Other researchers who have tried read like a roll call of famous names in science and mathematics: Onsager, Kac, Feynman, Fisher, Kasteleyn, Temperley, Green, Hurst, and more recently Barahona.
Says Sorin, ³What these brilliant mathematicians and physicists failed to do, indeed cannot be done.²
As for Ising, whom Sorin describes as ³a genius,² the young German-Jewish scientist was barred from teaching when Hitler came to power. The modeler worked menial jobs and, though he survived World War II and taught afterwards in the United States, never published again.
By Neal Singer
When a lake freezes over, how do trillions of randomly oriented water molecules know at almost the same time to align themselves into crystalline form? Similarly, when iron becomes magnetized, how do trillions of atoms know to align their spins almost instantly?
The best-studied model in science to discuss these phase changes and, indeed, a wide variety of changes in state (neural networking, protein folding, flocking birds, beating heart cells, questions of economics, and more) is the Ising model, developed by Ernst Ising in 1926 as part of his PhD dissertation.
Ising conceived of a linear chain, composed of particles that have magnetic moments called ³spins² able to take an up or down position. Each particle¹s spin influences the spins of the moments bordering it. The conception was expanded almost 20 years later into a two-dimensional grid of upward or downward spins, each spin influencing the behavior of spins around it, with a wider application in the material world.
The model can be expanded to any three-dimensional lattice model, and its properties figured out numerically with a high degree of accuracy. But not exactly. Not for the general case. As opposed to the known mathematical solutions for one or two dimensions, no one has been able to find an exact solution to any three-dimensional lattice problem in terms of elementary equations you could look up in a math book.
The continued application of Ising¹s model ‹ more than 8,000 papers published between 1969 to 1997 ‹ has tempted many scientists to extend the grid¹s usefulness into three dimensions, the realm in which most real-world problems take place.
Now Sandia computational biologist Sorin Istrail has shown that the solution of Ising¹s model cannot be extended into three dimensions for any lattice, and so exact solutions can never be found.
Sorin, who has just taken entrepreneurial leave from Sandia to accept the position of Senior Director of Informatics Research with Celera Genomics Corporation, says his paper will be published in May in the Proceedings of the Association for Computing Machinery¹s (ACM) 2000 Symposium on the Theory of Computing.
Says Sorin, ³Naturally, it¹s not as useful as finding the Holy Grail. We all wanna be like Lars [Onsager, the Nobel-Prize chemist who, in a mathematical tour-de-force, extended the Ising model solution from one dimension to two]. But at least no one now needs to spend time trying to solve the unsolvable.²
To prove that the solution could not be extended, Sorin resorted to a method called computational intractability, which identifies problems that cannot be solved in humanly feasible time. There are approximately 6,000 such problems known in all areas of science. They are all mathematically equivalent to each other. A solution to one would be a solution to all. Says Sorin, ³I showed that the Ising problem, for any lattice, is one of those problems. Therefore, it is computationally intractable.²
Nobel laureate Richard Feynman wrote in 1972 of the three-dimensional Ising model that ³the exact solution for three dimensions has not yet been found.²
Other researchers who have tried read like a roll call of famous names in science and mathematics: Onsager, Kac, Feynman, Fisher, Kasteleyn, Temperley, Green, Hurst, and more recently Barahona.
Says Sorin, ³What these brilliant mathematicians and physicists failed to do, indeed cannot be done.²
As for Ising, whom Sorin describes as ³a genius,² the young German-Jewish scientist was barred from teaching when Hitler came to power. The modeler worked menial jobs and, though he survived World War II and taught afterwards in the United States, never published again.
Comentários