Percolation and the complexity of games
- 1 January 1987
- journal article
- Published by IOP Publishing in Journal of Physics A: General Physics
- Vol. 20 (1) , L39-L43
- https://doi.org/10.1088/0305-4470/20/1/009
Abstract
The authors establish a connection between facet of the complexity of games and the problem of percolation on the underlying tree of winning strategies. They show that the complexity is minimal for both regular and totally random trees and identify a class of trees for which it is maximal.Keywords
This publication has 6 references indexed in Scilit:
- Complexity and the Relaxation of Hierarchical StructuresPhysical Review Letters, 1986
- Complexity and AdaptationPhysica D: Nonlinear Phenomena, 1986
- The average complexity of depth-first search with backtracking and cutoffIBM Journal of Research and Development, 1986
- Searching for an optimal path in a tree with random costsArtificial Intelligence, 1983
- Percolation theoryReports on Progress in Physics, 1980
- Some Cluster Size and Percolation ProblemsJournal of Mathematical Physics, 1961