[Updated June 30, 2021. Original article appeared July 17, 2020]
Problems come in three flavors: Easy to answer, hard to answer, and downright impossible. However, it’s not always clear which problems belong to which group. Many resist easy labeling: How do we know if it’s impossible to find a solution, or just stubborn? More philosophically: Is it beyond the reach of human knowledge?
The theory of computation focuses on why some problems are difficult and others aren’t. Its ideas reach beyond math and computer science, raising compelling questions in fields ranging from evolution to cellular behavior to social networks.
This summer, SFI’s Complexity Explorer — our online educational portal — offers its second course on the many faces of complexity, appropriate for learners from any background (and no mathematical heavy lifting required). SFI Professor Cris Moore, a resident faculty member who is a mathematician, computer scientist, and physicist, teaches the class, which spans five modules. A teaching assistant will be available to field questions and act as a guide for students.
“Computational complexity is a beautiful theory of why some problems are easy, and others are hard, and others are impossible,” says Moore. “It helps us understand why for some problems we can quickly zero in on a solution, or even see if a solution exists.”
Complexity affects anything that computes, which is a group that’s not limited to synthetic machines like laptops and smartphones. “Cells and markets and societies compute, in some way,” says Moore. “They process information. But they do it in very different ways than, for instance, computers do.”
Students will embark on a journey that’s both philosophical and educational. Moore not only unpacks the history and mechanics of the field, but also reveals complexity as a lens through which we can see the world. Beginning with simple problem-solving algorithms, students work their way through interdisciplinary search and optimization problems. They’ll also see how researchers think about these problems as vast, bumpy landscapes in which valleys represent possible solutions.
Like other offerings from Complexity Explorer, students can take it on their own timeline. “During the pandemic, we saw that people were looking for online content,” says SFI’s education director Carrie Cowan, “and we responded by making all of our courses available all the time.”
With the new class, Cowan says Moore takes a subject that might seem arcane and turns it inside-out, revealing what it says about the nature of curiosity itself. “He really gets into the subject from a philosophical sense,” she says. “What is the expanse of what can be known? What is unsolvable?”
The 2021 "Computation in Complex Systems" opens July 19, 2021. For more details, and to enroll, visit computation.complexityexplorer.org