3.3.3.2 Class NP
Algorithms and Problem Solving
Class NP refers to a category of problems for which, if a solution is given, it can be checked quickly by a computer. These are problems where verifying a proposed solution is easy, but finding that solution might be difficult and time-consuming.
Example
Consider a common example of solving a Sudoku puzzle. In Sudoku, you fill a 9 x 9 grid with numbers so that each row, column, and 3 x 3 sub grid contains all digits from 1 to 9 exactly once as shown in Figure 3.5.
Class NP and Sudoku
- Verification is Easy: If someone gives you a completed Sudoku grid, you can quickly check if the solution is correct. You just need to ensure that each row, column, and 3 x 3 sub grid contains all numbers from 1 to 9 without repeating.
- Finding the Solution is Hard: Solving Sudoku from scratch, especially larger or more complex puzzles, can be difficult and time-consuming. There is no simple, fast way to guarantee a solution, which means finding the solution is not always efficient.
- Non-deterministic Polynomial Time: Class NP problems can be solved quickly if given a correct solution, but finding that solution might take an impractically long time for large problems.
How It Works