3 docs tagged with "polynomial-time"

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 "solvable fast"? This post builds the formal definition of the complexity class P from the ground up — using sorting, binary search, and the contrast between polynomial and exponential growth.

If you can solve one problem, can you solve another? Reductions are the tool that lets us answer that question precisely — and they are the key to everything in Phase 2.