ACM Home Page
Please provide us with feedback. Feedback
Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intracatability for the partition function of the Ising model across non-planar surfaces (extended abstract)
Full text PdfPdf (1.04 MB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents
Portland, Oregon, United States
Pages: 87 - 96  
Year of Publication: 2000
ISBN:1-58113-184-4
Author
Sorin Istrail  Sandia National Laboratories, Applied Mathematics Department, MS 1110, Albuquerque, NM
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 11,   Downloads (12 Months): 69,   Citation Count: 4
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/335305.335316
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
F. Barahona. On the computational complexity of ising spin glass models. J. Phys. A: Math. Gen., 15:3241- 3253, 1982.
 
2
R. J. Baxter. Ezactly Solved Models in Statistical Mechanics. Academic Press, 1982.
 
3
N. L. Biggs. Interaction Models. Cambridge University Press, 1977.
 
4
S.' G. Brush. History of the lenz-ising model. Rev. Mod. Phys., 39, 1967.
 
5
W. Camp. Ising transfer matrix and a d-dimensional fermion model. Phys. Rev. BS, 9, 1973.
 
6
W. Camp and M. E. Fisher. Decay of order in classical many body systems: Introduction and fromal theory. Phys. Rev. B6, 3, 1972.
 
7
R. Feynman. Lectures on Statistical Mechanics. Addison-Wesley, 1972.
 
8
M. Fisher. On the dimer solution of the planar Ising model. J. Math. Phys., 7, 1966.
 
9
M. E. Fisher. Simple ising models still thrive. Physica, 106, 1981.
 
10
H. O. Georgii. Gibbs Measures and Phase Transitions. de Gruyter, 1988.
 
11
S. Goodman and S. Hedetniemi. Eulerian walks in graphs. SIAM J. Computing, 2, 1973.
 
12
F. O. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SiAM J. Computing, 4, 1975.
 
13
F. Harary. Feynman's simplification of the kac-ward treatment of the two-dimensional ising problem.
 
14
F. Harary, editor. Graph Theory and Theoretical Physiscs. Academic Press, 1967.
 
15
F. Harary. A graphical exposition of the ising problem. J. Australian Mathematical Society, 1971.
 
16
C. A. Hurst. Applicability of the pfaffian method to combinatorial problems on a lattice. Journal of Mathematical Physics, 3(1):90-100, 1964.
 
17
C. A. Hurst. Relation between the onsager and pfaffian methods for solving the ising problem, i. the rectangular lattice. Journal of Mathematical Physics, 6(1):11-18, 1965.
 
18
E. Ising. Beitrag zur theorie des ferromagnetismus. Z. Physics, 31, 1925.
 
19
F. Jaeger, D. L. Vertigan, and D. j. A. Welsh. On the computational complexity of the jones and tutte polynomials. Math. Proc. Camb. Phil. Soc., 108, 1990.
 
20
M. Jerrum. Two-dimensional monomer-dimer systems are computationally intractable, j. Star. Phys., 48(1), 1987.
 
21
 
22
M. Kac. Enigmas of Chance. Harper and Row, 1985.
 
23
M. Kac and J. C. Ward. A combinatorial solution of the two dimensional ising model. Phys. Rev., 88, 1952.
 
24
P. W. Kasteleyn. The statistics of dimers on a lattice. i. the number of dimers arrangements of a quadratic lattice. Physica, 27, 1961.
 
25
P. W. Kasteleyn. Graph theory and crystal physics. Graph Theory and Theoretical Physics (F. Harary ed.), 1967.
 
26
H. A. Kramers and Wannier. Statistics of the twodimensional ferromagnet, i and ii. Phys. Rev., 60, 1941.
 
27
 
28
B. M. McCoy and T. T. Wu. The Two-Dimensional Ising Model Harvard University Press, 1973.
 
29
E. W. Montroll. Lectures on the ising model of phase transitions. Statistical Physics, Phase Transitions and Superfluidity, Brandais University Summer Institute in Theoretical Physics, 2, 1968.
 
30
G. F. Newell and E. W. Montroll. On the theory of the ising model of ferromagnetism. Reviews of Modern Physics, 25(2):353-389, 1953.
 
31
L. Onsager. Crystal statistics i. a two'dimensional model with an order-disorder transition. Phys. Rev., 65, 1944.
 
32
G. I. Orlova and Y. G. Dorfman. Finding the maximum cut in a graph. Engr. Cybernetics, 10, 1972.
 
33
R. Peierls. Ising's model of ferromagnetism. Proc. Camb. Phil. Soc., 32, 1936.
 
34
S. Sherman. Combinatorial aspects of the ising model of ferromagnetism, i. a conjecture of feynman on paths and graphs. Journal of Mathematical Physics, 1(3):202- 217, 1960.
 
35
H. N. V. Temperley. Two-dimensional ising models. Phase transitions and critical phenomena (Domb, C. and Green, M. $. (ed)), 1, 1974.
 
36
D. J. A. Welsh. The computational complexity of some classical problems from statistical physics. Disorder in physical systems, pages 307-321, 1990.
 
37