Defining the Class NP
What does it actually mean for a problem to be "verifiable fast"? This post builds the formal definition of NP from the ground up, using the Rubik's Cube, Sudoku, and the strange but satisfying idea of a certificate.
What does it actually mean for a problem to be "verifiable fast"? This post builds the formal definition of NP from the ground up, using the Rubik's Cube, Sudoku, and the strange but satisfying idea of a certificate.