We defined the complexity class \(\mathsf{NP}\), but what does \(\mathsf{NP}\) stand for anyway? Does it stand for “Not Polynomial” or “No Polynomial”? It actually stands for “Non-Deterministic Polynomial Time”. It turns out the languages in \(\mathsf{NP}\) are precisely the ones that can be decided in polynomial time by a non-deterministic Turing machine. In this course, we do not introduce or talk about the non-deterministic Turing machine model. Instead, we define \(\mathsf{NP}\) using the concept of a verifier Turing machine. That being said, it is good to have some knowledge on where the name \(\mathsf{NP}\) comes from. If you take 15-455 “Undergraduate Complexity Theory” later on, you’ll see the non-deterministic Turing machine model and why it is equivalent to the verification definition we have given in this course.