Lesson 1

As we have seen, proofs are not only for theorems: in practice, we need proofs of facts about specific objects—for example, proofs that a given bipartite graph does not have a large matching or that a given system of linear inequalities has no solution. Usually, we prove that a given object has a certain property. For maximum generality, it turns out to be convenient to define the language of all objects with such a property.

A language \(L \subseteq \Sigma^{*}\) is a subset of strings of finite length over some finite alphabet \(\Sigma\). Our task will be to check the membership of a string \(x \in \Sigma^{*}\) in the language \(L\). This both generalizes the concept of proof in mathematics and includes various algorithmic problems:

• A mathematical theorem is simply a statement of the form “\(x \in L\)”, where \(x\) is a statement, and \(L\) is the language of true statements.


• Algorithmic problems are also naturally formulated in this way. Suppose, for example, it is necessary to check whether a given graph can be colored (properly) with three colors. Then \(x\) specifies the graph, and \(L\) is the language of all 3-colorable graphs. Many other decision problems (where it is necessary to check whether the input object has some property) are formulated in the same way. Optimization problems are usually formulated in terms of languages as follows: if it is necessary to maximize an objective function \(f\), then we consider that the language \(L\) consists of all pairs \((x,k)\) for which \(f(x) \le k\).