logoalt Hacker News

thaumasiotes • today at 8:29 PM • 0 replies • view on HN

> How do you explain NP in simple terms? "Things that are hard to compute?"

There's a very common answer to this question: NP is the space of questions for which, when someone claims to have the answer, it's easy for you to tell whether they're right.

"Where are my keys?" - NP.

"Should I marry my girlfriend?" - not NP.

(Where "easy" is defined as polynomial time.)