Hacker News new | ask | show | jobs
by smallnamespace 787 days ago
Have you ever heard the term NP-complete?
1 comments

Yeah, I mean, that's the joke.

The comment I replied to, "a huge class of problems that's extremely difficult to solve but very easy to check", sounded to me like an assertion that P != NP, which everyone takes for granted but actually hasn't been proved. If, contrary to all expectations, P = NP, then that huge class of problems wouldn't exist, right? Since they'd be in P, they'd actually be easy to solve as well.

We could end up with a non-constructive proof of P=NP. That is, a proof that the classes are equal but no algorithm to convert a problem in one into the other (or construct a solution of one into a solution of the other).