# Complexity Explorer Santa Fe Institute

This course is no longer in session. ## Computation in Complex Systems

• Two Kinds of Paths
• Polynomials vs. Exponentials
• Divide and Conquer
• Big O and All that
• When the details don't matter
• Quiz 1 (self-assessment)
• Exam
• Divide and Conquer Redux
• Dynamic Programming
• Greedy Algorithms
• Reductions and Translations
• Lessons So Far
• The Best of All Possible Algorithms
• Complexity Wrap-Up
• Quiz 2 (self-assessment)
• Exam
• Finding versus Checking
• Circuits and Formulas
• More NP-complete Problems
• P versus NP Problem
• Existence and Nonexistence
• Above and Beyond
• Exam
• Real World Problems
• Phase Transitions
• Random Problems
• Solvability Threshold
• Modeling Differential Equations
• Landscapes, Clustering, Freezing, and Hardness
• Exam
• Building Blocks: Recursive Functions
• Building Blocks: Partial Recursive Functions
• λ Calculus
• Turing Machines
• The Halting Problem
• The Grand Unified Theory of Computation
• The Analytical Engine
• Cellular Automata
• Tile-Based Computation
• Dynamical Systems
• Quiz 5 (self-assessment)
• Exam
• More from Cris Moore
• Other ComplexityExplorer resources

## Site Percolation: demonstration

Site percolation applies to the spread of information. Information here can take many forms - for instance, a virus spreading in the population or a wildfire spreading in a forest. The substrate over which the information spreads is modeled as a lattice. The lattice can have different porosities, or densities - for instance, the percentage of people susceptible to the virus or the percentage of forest area occupied by trees. There is a threshold density at which the spread of information is complete, i.e. traverses the lattice from end to end.

The demonstration depicts percolation as flow into a porous lattice - imagine water dripping into a filter full of ground coffee. The flow starts from the top of the diagram. You can change the porosity of the lattice to discover the conditions that allow the flow to traverse the lattice - that allow you to make coffee.