Statistical mechanics and combinatorial optimization

1

F. Barahona.
On the computational complexity of ising spin glass models.
J. Phys. A: Math. Gen., 15:3241-3253, 1982.

2

M. Biafore.
Universal computation in few-body automata.
Complex Systems, (7):221-239, 1993.

3

S. Dube.
Undecidable problems in fractal geometry.
Complex Systems, 7:423-444, 1993.

4

E. Goles and M. Margenstern.
Sand pile as a universal computer.
Int. J. of Modern Physics C, 7(2):113-122, 1996.

5

K. Culik II and S. Yu.
Undecidability of ca classification schemes.
Complex Systems, pages 177-190, 1988.

6

A.R. Smith III.
Simple computation-universal cellular spaces.
Journal of the Association for Computing Machinery, 18:339-353, 1971.

7

K. Lindgren and M.G. Nordahl.
Universal computation in simple one dimensional cellular automata.
Complex Systems, 4:299-318, 1990.

8

J. Machta.
The computational complexity of the self-avoiding walk on random lattices.
J. Phys. A: Math. Gen., 25:521-527, 1992.

9

J. Machta.
The computational complexity of pattern formation.
J. of Stat. Phys., 70(3/4):949-965, 1993.

10

J. Machta and R. Greenlaw.
The computational complexity of generating random fractals.
Technical report, University of Massachusetts, 1995.

11

J. Machta and R. Greenlaw.
Parallel computational complexity and logical depth in statistical physics.
In T. Toffoli, M. Biafore, and J. Le ao, editors, 4th Workshop on Physics and Computation, pages 201-207, 1996.

12

J. Machta and K. Moriarty.
The computational complexity of the lorentz lattice gas.
Journal of statistical physics, 87(5/6):1245-1252, 1997.

13

C. Moore.
Unpredictability and undecidability in dynamical systems.
Phys. Rev. Let., 64(20):2354-2357, 1990.

14

C. Moore.
Generalized shifts: unpredictability and undecidability in dynamical systems.
Nonlinearity, (4):199-230, 1991.

15

C. Moore.
Majority-vote cellular automata, ising dynamics, and p-completeness.
Technical report, Santa Fe Institute, August 1996.

16

C. Moore and M.G. Nordhal.
Lattice gas prediction is p-complete.
Technical Report SFI 97-04-043, Santa Fe Institute, 1997.

17

R.K. Squier and K. Steiglitz.
Two-dimensional fhp lattice gases are computation universal.
Complex Systems, 7:297-307, 1993.

18

S. Wolfram.
Undecidability and intractability in theoretical physics.
Phys. Rev. Let., 54:735-738, 1985.