Complexity Explorer Santa Few Institute

Computation in Complex Systems (Spring 2023)

Lead instructor:

This course is no longer in session.


The course is composed of five units, each with about one hour of lecture videos, accompanied by exercises, quizzes and a unit exam. Units include:

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

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 (see Subtitles & Transcripts below for more on language accessibility).

A complete subject list for each unit can be found here. 





Participants should expect to spend about 5-8 hours per week watching lectures, working through problems, and taking quizzes and exams, and completing peer-grading assignments.


All necessary materials for the course are provided from within the Complexity Explorer site. The videos are always available on our YouTube channel. Other course materials such as quizzes, simulations and exams are only available through the Complexity Explorer course and will not be accessible after the course is closed.

No textbook is required.  The lectures will be complemented by suggested readings that will be provided on the course web site. If you would like a textbook, the course was inspired by the first part of Cris Moore's and Stephan Merten's textbook The Nature of Computation


Each unit consists of a series of short videos corresponding to several subtopics within the main topic of the unit. The course site and YouTube playlist present the videos in a fixed order, but you are welcome to skip, repeat and otherwise watch the videos in whatever order you prefer. Each unit also contains quizzes (introduced in the videos). Some units contain interactive excercises or simulations to illustrate certain concepts.

At the conclusion of each unit, you will find a quiz and an exam. Quizzes are intended to help you assess your understanding of the material. Quizzes do not form part of the course grade. The exams generally consist of two questions, taken directly from the video quizzes interspersed throughout the unit. The exams are all peer-graded. Your score on exams determines your score in the course and thus successful completion of the course.


How does the peer review system work? At the end of each unit, there will be an exam for which you will submit work to be reviewed by your peers. You will also be expected to review the exam answers submitted by your fellow course participants. A detailed grading rubric will be provided to help you grade the exams and ensure consistency among scores. Each exam will be scored by three peer graders. Likewise, you will be expected to grade three exams.

In order to pass the peer review section, you need to do two things:

1. Submit your assignment before the submission deadline.

2. Review three exams before the evaluation deadline.

Once the peer-grading assignment has been created, you can find the peer-review section(s) quickly by clicking on the "My Progress" tab, and then clicking on the appropriate section of the Homework/Exam column.  

To submit an assignment, upload the document.  Make sure your name is not on your assignment.

To grade other exams, go to the peer review section and you will be prompted to download a file with one assignment. Follow the grading rubric provided, add your comments to the comment box (required), and submit.  Once complete, you will have access to a second exam, and after that, a third.  Please ensure you have completed all the reviews before the evaluation deadline in order to receive your full score. You should receive a reminder email about the submission and evaluation deadlines 24 hours before they are due. 

How is the exam grade determined? When you submit a peer-graded exam, you will receive an average score based on the three scores assigned. This score count as 2/3 of the grade.  The remaining 1/3 of the grade is a fixed score, allocated automatically when you have submitted grades for the three peer exams assigned to you.

After completing the three peer-grading assignments, you may continue to see more exams to review in the queue. Why? You are required to submit grades for three exams in order to recieve full credit on the exam, but optional peer-grading assignments will be offered to help ensure that every submission is reviewed at least three times. (For example, if an exam is sitting in the grading queue, still ungraded, those ungraded exams will be offered to other participants - just in case the originally assigned grader does not complete the assignment.)  You are welcome to review as many exams as you like. You are equally welcome to stop after three.


How is the course graded? Your final grade will be based on a compilation of the end-of-unit exams, described above. Your total course score will be your average score over these tests and the peer-reviewed assignment.  Your scores are only meant for your own assessment of your progress in the course and to determine successful completion (see below).


How can I receive a certificate of completion? Will the certificate list my grade? You need to have submitted all of the end-of-unit exams and completed the peer-grading assignments in order to be eligible to recieve a certificate of completion. In addition, you must recieve an average score of 60% or more on the exams by the course end date in order to receive a certificate of successful completion.   Note:  You don't need to get 60% or greater on each test, only on the average overall tests. The certificate will not list your total score; it will simply say that you have successfully completed this course.  You will be able to print out a copy of your progress report at any time during or after the course.

Can I get university credit for this course? Not through Complexity Explorer or the Santa Fe Institute. We do not partner with any degree-granting institutions. If you are enrolled at a university and find the course valuable, you can make your professors aware of the course and suggest they incorporate the content into a for-credit course.

Will I get any kind of certificate? Everyone who successfully completes the course will receive a certificate of completion from the Santa Fe Institute. This is a digital certificate; we do not offer printed certificates at this time.


We do not employ any technologies to assess whether participants are submitting original work in their exam answers or otherwise working independently on exams, quizzes, etc. (See also COLLABORATION below.) We hope that participants come to Complexity Explorer courses with the primary intent to learn the material, not - or not only - to get a certificate of completion. Submitting copy-paste answers in response to an exam prompt does not facilitate learning, and thus we hope that participants will not engage in such activities. Ultimately, it is up to each participant to decide what they want to achieve in the course and how to best accomplish their goals.


What are the rules on collaboration? You are welcome to discuss anything with anyone!  The course site hosts a forum for participants to discuss the course content, homework, etc. We do ask that the end-of-unit exams be taken individually. We rely on an honor system and do not employ technologies to indicate whether or not participants adhere to this expectation.

What is the forum? The course site hosts a forum in which course participants can post questions, answer other people's questions, and discuss the course material or related topics. The forum is monitored by the teaching assistant and Complexity Explorer staff. Questions posted to this forum will be answered by the instructor, teaching assistant, and/or other students.


Who is the intended audience and what are the prerequisites? 

Anyone is who is interested in computation with varying degrees of past training.  The prerequisites for individual lectures range from none at all to basic computational theory and computer science.  This course will likely be understandable for upper-level undergraduates and beyond. This is an excellent introductory level course for anyone.


Do I need special software to complete the course? No, Complexity Explorer works on standard web browsers. The video content embedded within Complexity Explorer is hosted on YouTube and thus may encounter firewall blocks, so download options are available (see below). There is no coding required for the course. Participants with knowledge of a programming language may find that some exercises are fun coding challenges, in which case a Python, R, or other language interface may be helpful.

How do I get the videos to play at a different rate?  Our videos are streamed through YouTube, which provides an option to control the playback rate.

Can I watch the videos without YouTube?  Yes, you can download all of the videos from AWS and watch them locally. (see next point)

Can I download the videos? Yes, click on the "Download" button that appears above the video screen within the Complexity Explorer course. The complete video collection for each unit will be made available as a bulk download on the Supplementary Materials page. 


Are subtitles available?  YouTube AI-generated subtitles are available in English for most lectures and are reasonably accurate. Additionally, Complexity Explorer hosts an ongoing effort to create subtitles in different languages.  If subtitles are available for a given video they can be accessed from the YouTube "CC" menu button.  

Can I download a text transcript of the video? For any video that has subtitles available, there will also be a plain text transcript (in .txt format) available for download, for each subtitle language available.  When you click on Subtitles & Transcripts you will be given all of the language options available, and you can choose to download either the subtitle or the transcript, or both.  


Do I have to enroll to take the course?   You need to enroll in order to access the complete course materials and receive a certificate of completion at the conclusion of the course.  Enrollment is easy. We do not share your data with anyone and you are welcome to unenroll from the course at any time (see below).

How do I enroll?  Follow this link - - and click the “Enroll” button in the upper right section of the course homepage (immediately below the "Home", "About", "Explore", etc. menu). You will be guided through the short enrollment process. Course content will not be available until the course starts on July 15.

How do I unenroll? If you decide that you would like to unenroll for whatever reason, this option is available through the text button labeled "Unenroll" in the upper right section of the course homepage (immediately below the "Home", "About", "Explore", etc. menu). If you made a donation for the course and decide to unenroll, please contact so that we can discuss a deferral to another instance of the course. Note that we can not refund donations.

Can I enroll after the course begins? To receive a grade and a certificate, you must enroll before the first exam. 

I don't want to take the course for a certificate and I don't care about exams. Can I access the content without enrolling? Yes, you can find all of the course lectures on our YouTube channel, under the "Computation in Complex Systems" playlist.


In what ways am I allowed to use these resources?  All the materials on this site are available for your use for any non-commercial purpose. All materials (videos, code, write-ups, etc.) are covered by the Creative Commons Attribution-NonCommercial-ShareAlike License ( ). This states that you may copy, distribute, and transmit the work under the condition that you give attribution to, and your use is for non-commercial purposes.


Please address any other questions to