Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: Two-Dimensional Monomer-Dimer Systems are Computationally Intractable
Автор: Jerrum M.
The classic problem of counting monomer-dimer arrangements on a twodimensional lattice is analyzed using techniques from theoretical computer science. Under a certain assumption, made precise in the text, it can be shown that the general problem is computationally intractable. This negative result contrasts with the special case of a system with monomer density zero, for which efficient solutions have been known for some time. A second, much easier result, obtained under the same assumption, is that the partition function of a three-dimensional Ising system is computationally intractable. Again, the negative result contrasts with known efficient techniques for evaluating the partition function of a two-dimensional system.