Hacker News
points by Dylan16807 10 hours ago | 0 comments
Clearly show it how?

It's not enough for finding a solution to be slower than verifying, it has to be slower by a particular extreme amount, and that has to hold for the best possible solution.

Also, there's a set of problems called NP-hard that you can convert any other NP problem into. For P≠NP we have to make sure all of the problems that are NP-hard have that speed difference (including the overhead from doing that conversion).

Aún no hay comentarios.
Hacker News