2 docs tagged with "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.

The gap between finding an answer and checking one feels obvious the moment you see it. This post asks why that obvious gap is also the deepest open question in all of computer science.