About this course
Explore what computation can and cannot do. The lectures progress through automata, formal languages and Turing machines toward computability, complexity and provably difficult problems.
Topics and lesson examples
- 1. Introduction, Finite Automata, Regular Expressions
- 7. Decision Problems for Automata and Grammars
- 14. P and NP, SAT, Poly-Time Reducibility
- 20. L and NL, NL = coNL
- 26. coNP is a subset of IP
Course at a glance
| Provider | MIT |
|---|---|
| Platform | YouTube · MIT OpenCourseWare |
| Access | Free Video |
| Level | Intermediate — Coursya study-level assessment |
| Language | English |
| Available lessons | 25 |
| Video duration | 32h 18m · self-paced |
| Details checked | 10 October 2026 |
Preparation and study approach
Suggested preparation: Discrete mathematics, proof-writing and programming.
Follow the available videos in sequence, pausing to summarize the main argument or reconstruct a worked example. Keep a short list of assumptions, unfamiliar terms and questions to revisit. Additional reading, problem solving and practice will take time beyond the listed video duration.
Using this video classroom
Select a lesson from the list, or search for a topic. Previous and Next move through the sequence. You can mark lessons complete; progress is stored in this browser without a Coursya account.
Free access and course scope
The public MIT OpenCourseWare videos in this classroom are free to watch. This listing provides the available playlist recordings, which may include selected lectures, recitations, demonstrations or supporting discussions rather than every component of the original campus course. Textbooks, equipment, software licenses, supervised labs, graded assignments and instructor feedback are not supplied by Coursya. No purchase is required to watch the videos or use the note-based study approach above.
Coursya independently organizes these resources for self-paced study. Watching does not award an MIT certificate, academic credit or admission to MIT.
Video provider and credit: MIT OpenCourseWare on YouTube. Coursya titles, descriptions and cover artwork are independently prepared.
Related courses for your next step
Provider: MIT. Videos play from the MIT OpenCourseWare channel on YouTube.
Report a correction
Questions & discussion
Share a useful question or correction. Comments appear after moderation. Please avoid personal or sensitive information.