Sustainability or collapse follow from the success or failure of problem-solving institutions. The factors that lead to long-term success or failure in problem solving have received little attention, so that this fundamental activity is poorly understood. The capacity of institutions to solve problems changes over time, suggesting that a science of problem solving, and thus a science of sustainability, must be historical. Complexity is a primary problem-solving strategy, which is often successful in the short-term, but cumulatively may become detrimental to sustainability. Historical case studies illustrate different outcomes to long-term development of complexity in problem solving. These cases clarify future options for contemporary societies: collapse, simplification, or increasing complexity based on increasing energy subsidies.