圣塔菲课程：Computation in Complex Systems (Summer 2020)
About the Course:
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.
1.Easy and Hard
2.Algorithms and Landscapes
3.P versus NP
4.Worst-case, Natural, and Random
Units will be released approximately one per week, with a unit exam at the end of each and due by the end of the subsequent week (eg. unit 1 released at start of week 1; unit 1 exam due at the end of week 2). Each unit will require an average of about 5 hours to complete (including all content and assessments). All coursework is conducted in English.
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.