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 AaronsonEvidence 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”
Created: 6/13/2026, 12:26:25 AM
Your notes
Loading notes...