Lesson 1

When discussing proof systems and algorithms, we did not talk about runtime. In this section, we will impose an additional constraint: now we will talk not just about algorithms and proofs, but about fast algorithms and short proofs. Thus, we will move from questions of computability theory to questions of computational complexity theory.

The class P is the class of languages for which there is a deciding algorithm whose runtime is polynomial. This class includes many well-known decision problems: checking whether a graph is 2-colorable, checking a number for primality, checking whether the distance between two vertices is at most a given value, and so on.

The class NP is the class of languages \(L\) for which there is a proof system \(S\) with an additional constraint: the runtime of the algorithm \(S\) must be bounded above by a polynomial in the length of \(x\). It follows that for each \(x \in L\), there must exist a proof \(w\) whose length is no more than a polynomial in the length of \(x\).