Complexity Explorer Santa Fe Institute

This course explores computational complexity, from search algorithms and solution landscapes to reductions and universality. We explore problems ranging from easy (polynomial time) to hard (NP-complete) to impossible (undecidable). These ideas form one of the most beautiful fields of modern mathematics, and they are increasingly relevant to sciences ranging from physics to biology. The aim of this course is to help participants gain an understanding of the deep ideas of theoretical computer science in a clear and enjoyable fashion, making those ideas accessible both to non-computer scientists and to computer scientists who want to revisit these ideas in a broader and deeper way.

Units include:

1. Easy and Hard
2. Algorithms and Landscapes
3. P versus NP
4. Worst-case, Natural, and Random
5. Computation Everywhere

Cristopher Moore - Course Creator

Cris Moore is resident faculty at the Santa Fe Institute. He received his B.A. in Physics, Mathematics, and Integrated Science from Northwestern University, and his Ph.D. in Physics from Cornell. From 2000 to 2012 he was a professor at the University of New Mexico, with joint appointments in Computer Science and Physics. He has also held visiting positions at École Normale Superieure, École Polytechnique, Université Paris 7, École Normale Superieure de Lyon, the University of Michigan, and Northeastern University. He has written 150 papers at the boundary between physics and computer science, ranging from quantum computing, to phase transitions in NP-complete problems, to the theory of social networks and efficient algorithms for analyzing their structure. He is an elected Fellow of the American Physical Society, the American Mathematical Society, and the American Association for the Advancement of Science. With Stephan Mertens, he is the author of The Nature of Computation from Oxford University Press. 

John Malloy (he/him) - Course Developer

John is a PhD student at Arizona State University. He received his B.S. in Bioinformatics and Computational Biology from University of Maryland, Baltimore County, as well as a M.F.A in Teaching from Notre Dame of Maryland University. He studies astrobiology, the search for life on other planets, through exploring the evolution of network-based systems with non-biological evolutionary pressures. Through systems such as pharmaceutical chemistry and scientific citation networks, he hopes to quantify evolutionary patterns which apply to non-DNA-based life. Outside of astrobiology, he can be found working to advance science-based policy measures in Arizona and training for ultramarathons throughout the American Southwest.