3 ms·
Have you ever heard the term NP-complete?
by smallnamespace 2y ago
Have you ever heard the term NP-complete?
- losvedir 2y agoYeah, 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.
- acchow 2y agoWe 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).