definition

Definition of NP and the Check-vs-Solve Asymmetry

A problem is in NP if, whenever its answer is yes, a solution can be exhibited and verified in polynomial time — like a completed jigsaw puzzle, prime factors that can be checked by multiplying, a solved Sudoku, or an optimization solution shown to a client — capturing the asymmetry between hard-to-solve but easy-to-check problems.

definitionpending

Speaker

Scott Aaronson

Evidence Quote

“A problem is in NP if whenever the answer to it is, yes, meaning like, yes, there is a solution, then someone can show you the solution and you could check the solution using a polynomial-time algorithm”

Source

99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity— Sean Carroll's Mindscape
Created: 6/13/2026, 12:26:25 AM

Your notes

Loading notes...