Lesson 2

We are surrounded by many problems that naturally fall into the class NP.

• Sudoku.  In the puzzle Sudoku, a \(9 \times 9\) grid is given, with some cells already filled with digits from \(1\) to \(9\). The task is to fill the empty cells so that each column, each row, and each of the nine \(3 \times 3\) squares contain all different digits (or report that it is impossible). Sudoku has a natural generalization to an \(n \times n\) grid. The proof of membership in the corresponding language is simply the solution. Of course, such a solution is short.
  

  



• Graph Isomorphism.  In the graph isomorphism problem, two (undirected) graphs with \(n\) vertices are given, and it is required to check whether their vertices can be numbered with numbers from \([n]\) so that their edges match as sets. If they can, then the two graphs are called isomorphic.
  In the figure below, graphs \(G_{1}\) and \(G_{2}\) are isomorphic to each other and not isomorphic to \(G_{0}\).
  

  



• Graph Coloring.  Given a graph and a number \(k\). The question is whether its vertices can be colored with \(k\) colors so that the ends of each edge are of different colors.