MIT OpenCourseWare's version of 18.404J, the graduate-level Theory of Computation course taught by Michael Sipser, covering automata, computability, and complexity theory including P vs NP. Its lecture materials are freely available online.

Commenters point to it as a freely available course on the theory of computation, with one saying they highly recommend it for understanding P and NP.

What commenters said (2)

1. Strongly recommendsnlewycky2023in “P vs NP: The most important unsolved problem in computer science”

   - “p” - a category of problems which can be solved in O(n²)

   - “np” - a category of problems which can be checked, but not solved, in O(n²)

   These definitions are incorrect. Certainly there are other polynomials than just n². P is the complexity class wherein the problem can be solved on a Turing machine in a number of steps equal to some polynomial of the size of the input. For NP, replace "Turing machine" with "nondeterministic Turing machine" and otherwise it's the same. The 'size of the input' is the count of symbols on the machine's tape, allowing for the input to be written in any finite alphabet, chosen by the designer of the Turing machine.

   Nondeterministic can mean different things in different contexts, so I want to clarify. Here, nondeterministic means that the machine does the 'impossible' thing of forking itself and running up to an infinite number of copies of the deterministic machines (including distinct copies of their state) at the same time, then if one of the computations succeeds then that computation is kept and the others are discarded (including the count of how many steps they spent). This is why, if you have a machine that can check a problem in P, you can make the machine to solve it in NP by wrapping your checker in "use nondeterminism to generate every possible input value" and simultaneously check them all.

   I highly recommend the theory of computation course at MIT, which is freely available online:

   https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/ https://www.youtube.com/playlist?list=PLidiQIHRzpXIFFbyGrWkqXXVj0BztDcTF

   I found the course very approachable.

   All information necessary to generate checkable solutions to any problem must be encoded in the problem itself, or the problem would be undecidable, because there would be no way to check a solution against a problem if the problem and solution were completely unrelated.

   This is actually a great insight, but you must keep in mind that if I tell you that the solution to "a > b" is True, you cannot find a and b. You are touching on an important concept in computer science theory called "reversible computing". It's also related to information theory. If I have a machine that solves the travelling salesman problem that outputs "the fastest route is from B to C to A", then you must ask yourself whether there are multiple different inputs to the problem which can generate that output? (You don't always have the freedom to change the input type of the problem, or else I could factor integers in constant time by demanding that all integers must be input as a product of primes.)

   When the values are computable from the other, the question remains about the number of steps it takes to do. You still have to show that it's bounded above by some polynomial, and then that this is true for all problems in NP. We already have ways to rewrite one NP problem into another, and so showing a single machine that takes polynomial steps to solve any of those NP problems would suffice to show that P = NP. This is how we've proven lots of complexity classes the same in the past. On the other hand, we have almost no techniques which prove that two complexity classes are distinct.

2. Mentionsjacobolus2008in “Ask YC: Rigorous CS curriculum with dedicated students?”

   Harvard's CS department seems pretty decent (dedicated, interesting students; a variety of challenging courses; etc) to me, though as a non-CS-concentrator myself, I'm probably not the best one for advice. :) Also, I'm not sure whether you'll find much in the way of Ajax or similar technologies, but I'm far from convinced that you really want to take courses in that sort of thing. I was somewhat unimpressed with the intro theory course--would have been better to walk down the street and take Sipser's course at MIT.

   As you mentioned, one big thing to consider is what you are interested in besides CS, what other types of students you want to hang out with, etc. College, at least at good American schools, is generally less about preparation for a career, and more about personal growth and exploration.

   Finally, I imagine Stanford has somewhat better weather than Boston. :)

Related courses

• Algorithms, Part ICoursera · 38 recommenders
• CS61A: Structure and Interpretation of Computer ProgramsUC Berkeley · 31 recommenders
• 6.006 Introduction to AlgorithmsMIT OpenCourseWare · 27 recommenders
• Introduction to Computer Science and Programming in PythonMIT OpenCourseWare · 25 recommenders
• Algorithms: Design and Analysis, Part 1Coursera · 17 recommenders
• Algorithms, Part IICoursera · 11 recommenders
• Discrete OptimizationCoursera · 12 recommenders
• How to Code: Simple DataedX · 10 recommenders