*Hidetoshi Nishimori*

- Published in print:
- 2001
- Published Online:
- January 2010
- ISBN:
- 9780198509417
- eISBN:
- 9780191709081
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198509417.003.0009
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics ...
More

A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.Less

A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.

*Matthew Cook*

- Published in print:
- 2003
- Published Online:
- November 2020
- ISBN:
- 9780195137170
- eISBN:
- 9780197561652
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780195137170.003.0008
- Subject:
- Computer Science, Systems Analysis and Design

In Conway’s Game of Life [2], if one starts with a large array of randomly set cells, then after around twenty thousand generations one will see that all motion has ...
More

In Conway’s Game of Life [2], if one starts with a large array of randomly set cells, then after around twenty thousand generations one will see that all motion has died down, and only stationary objects of low period remain, providing a final density of about .0287. No methods are known for proving rigorously that this behavior should occur, but it is reliably observed in simulations. This brings up several interesting related questions. Why does this “freezing” occur? After everything has frozen, what is the remaining debris composed of? Is there some construction that can “eat through” the debris? If we start with an infinitely large random grid, so that all constructions appear somewhere, what will the long term behavior be? It seems clear that knowing the composition of typical debris is central to many such questions. Much effort has gone into analyzing the objects that occur in such stationary debris, as well as into determining what stationary objects can exist at all in Life [4, 8], Both of these endeavors depend on having some notion of what an “object” is in the first place. One simple notion is that of an island, a maximal set of live cells connected to each other by paths of purely live cells. But many common objects, such as the “aircraft carrier,” are not connected so strongly. They are composed of more than one island, but we think of them as a single object anyway, since their constituent islands are not separately stable. Any pattern that is stable (has period one, i.e., does not change over time) is called a still life. Since a collection of stable objects can satisfy this definition, the term strict still life is used to refer to a single indivisible stable object, and pseudo still life is used to refer to a stable pattern that is composed of distinct strict still lifes. For example, the bi-block is a pseudo still life, since it is composed of two blocks, but the aircraft carrier is a strict still life, since its islands are not stable on their own.
Less

In Conway’s Game of Life [2], if one starts with a large array of randomly set cells, then after around twenty thousand generations one will see that all motion has died down, and only stationary objects of low period remain, providing a final density of about .0287. No methods are known for proving rigorously that this behavior should occur, but it is reliably observed in simulations. This brings up several interesting related questions. Why does this “freezing” occur? After everything has frozen, what is the remaining debris composed of? Is there some construction that can “eat through” the debris? If we start with an infinitely large random grid, so that all constructions appear somewhere, what will the long term behavior be? It seems clear that knowing the composition of typical debris is central to many such questions. Much effort has gone into analyzing the objects that occur in such stationary debris, as well as into determining what stationary objects can exist at all in Life [4, 8], Both of these endeavors depend on having some notion of what an “object” is in the first place. One simple notion is that of an island, a maximal set of live cells connected to each other by paths of purely live cells. But many common objects, such as the “aircraft carrier,” are not connected so strongly. They are composed of more than one island, but we think of them as a single object anyway, since their constituent islands are not separately stable. Any pattern that is stable (has period one, i.e., does not change over time) is called a still life. Since a collection of stable objects can satisfy this definition, the term strict still life is used to refer to a single indivisible stable object, and pseudo still life is used to refer to a stable pattern that is composed of distinct strict still lifes. For example, the bi-block is a pseudo still life, since it is composed of two blocks, but the aircraft carrier is a strict still life, since its islands are not stable on their own.