# Complexity Explorer Santa Fe Institute

This course is no longer in session. ## Computation in Complex Systems (summer 2021)

• Course Introduction
• 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

## Hamiltonian Path

In graph theory, a Hamiltonian path is a path – or trace – through a graph that visits each vertex (node) exactly once. If the beginning and ending vertices are adjacent, the path is known as a Hamiltonian cycle. A graph that contains a Hamiltonian path is a traceable graph.

Hamiltonian paths are named after Sir William Rowan Hamilton, an Irish mathematician and astronomer. He developed the icosion game in which players were to find a Hamiltonian cycle in the edges of a dodecahedron.

In the interactive below, you can click your way through a two-dimensional planar dodecahedron graph to trace a Hamiltonian path. Reset the game using the "refresh" arrow.