One fun fact is that Sudoku (on a n by n grid) is NP-complete. It's in NP because given a sudoku problem instance (a n by n grid with only some clues filled in

One fun fact is that Sudoku (on a n by n grid) is NP-complete. It's in NP because given a sudoku problem instance (a n by n grid with only some clues filled in) and a proposed solution (a n by n grid with all the squares filled in) you can check if the solution is correct in polynomial time. That is, you check that each square in the problem is equal to the square in the solution, and you check the rows/columns/larger-squares to see if they each contain the values (1..n). So a problem X is in NP if given a polynomial-sized certificate C, you can run a polynomial-time algorithm C_Check() to see if it is actually a valid solution. In the sudoku problem: X is Sudoku with instance x C is the proposed solved sudoku C_Check(x, C) is the algorithm where you check the rows/columns/larger-squares and you check that for every square in X[i][j] that is filled, C[i][j] == X[i][j] In a normal breadth first search, where there are a polynomial # of vertices, you actually don't even need to use C until the very end. You're allowed to say X is ShortestPathProblem with instance x C is the proposed shortest path C_Check(x, C) is just (BFS(x) == C) So therefore any problem in P is automatically in NP.