Statistical Mechanics, Three-Dimensionality and NP-Completeness: I. Universality of Intractability of the Partition Functions of the Ising Model Across Non-Planar Lattices

This work provides an exact characterization, across crystal lattices, of the computational tractability frontier for the partition functions of several Ising models. Our results show that beyond planarity computing partition functions is NP-complete. We provide rigorous solutions to several working conjectures in the statistical mechanics literature, such as the Crossed-Bonds conjecture, and the impossibility to compute effectively the partition functions for any three-dimensional lattice Ising model; these conjectures apply to the Onsager algebraic method, the Fermion operators method, and the combinatorial method based on Pfaffians. The fundamental results of the area, including those of Onsager, Kac, Feynman, Fisher, Kasteleyn, Temperley, Green, Hurst and more recently Barahona: • for every Planar crystal lattice the partition functions for the finite sublattices can be computed in polynomial-time, paired with the results of this paper: • for every Non-Planar crystal lattice computing the parition functions for the finite sublattices is NP-complete, provide an exact characterization for several of the most studied Ising models. Our results settle at once, for several models, (1) the 2D non-planar vs. 2D planar, (2) the next-nearest neighbour *Research supported by the DOE, MICS Program DEAC04-94AL85000 interactions vs. 2D, and (3) the general 3D Ising, intensively studied open problems of the area. Our results axe obtained by establishing a Kuratowski-like charcterization theorem for the class of (infinite) crystal lattices called Bravais lattices, that can also be extended to general crystal structures. The "forbidden subgraph," called Kuratowskian, plays the central role, being contained in every non-planar crystal lattice. This universality phenomenon (existence independent of lattice structure), captured in the "equation": Translational Invariance + NonPlanarity = Universality of Subgraphs, provides a unified understanding of non-planarity as a root of computational intractability. The important structural property of the Kuratowskians is that they are "embedding-universal" for 3regular graphs, in the sense that every such graph has a subdivision included in the Kuratowskian. Several NP-hardness results are obtained in this paper, by using different types of Kuratowskians, which in turn witness NP-hardness of various counting coefficients of the partition functions. The exceedingly complex mathematical methods that solved the planar cases of the Ising model, could be interpreted as an explanation of why no 3D solvable cases have been found. Richard Feynman in 1972 commented " The exact solution for three dimensions has not yet been found". Our results, for the Ising models that we consider in this paper, provide evidence of a paradigm-shift: the "has not yet been found" needs now be replaced with "it may be computationally intractable across lattices." Th i s paper i s authored by an emplo yee(s) of the [U. S. ] Government and is in the public domain. STOC 2000 Portland Oregon USA 1-58113-184-4/00/5 1, INTRODUCTION 1.1 The Search for Exactly Solved Models in Statistical Mechanics One of the most exciting periods in statistical mechanics was in 1944, with the discovery by Laxs Onsager of the first exactly solved model that exhibits a provable phase tran-