# Complexity Explorer Santa Few Institute

## Computation in Complex Systems (Spring 2022)

This course is no longer in session.

• Course Introduction
• Two Kinds of Paths
• Polynomials vs. Exponentials
• Divide and Conquer
• Big O and All that
• When the details don't matter
• Exam
• Divide and Conquer Redux
• Dynamic Programming
• Greedy Algorithms
• Reductions and Translations
• Lessons So Far
• The Best of All Possible Algorithms
• Complexity Wrap-Up
• 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
• Exam
• More from Cris Moore
• Other ComplexityExplorer resources

## Percolation: criticality & the giant component

Percolation theory was conceptualized by Paul Flory and then extended by Walter Stockmeyer, both chemists studying polymers. (Flory would later win the Nobel Prize for his work on macromolecules.) Both were interested in the phase transition from a liquid to a gel of polymers in solution. Through chemical cross-linking, polymers become increasingly interconnected until they behave as a network solid. The Flory-Stockmeyer theory predicts the gel point (phase transition) of the system given the concentrations of a branching units and linear linkage units.

When applying percolation theory to graphs, Flory's and Stockmeyer's critical concentration for polymer gelation can be thought of as the critical probability density of occupied sites in a lattice that allows for a continuous path from one side of the lattice to the opposite side. This spanning path is the giant component. Just as at low polymer concentration, no gel will form, likewise, at low probability density, no giant component will form. Try it out!

## More About Percolation

On a square lattice of side length L, each of the N = L x L lattice site is occupied with probability p. when two occupied sites touch, they connect to build a component. If a third site touches one of those two, it belongs to the same component and so forth. With increasing occupation probability p, larger clusters appear.