Hacker News Reader

If P=NP, then finding an algorithm is, by certain definition, exactly as easy as proving an algorithm correct! This is, after all, the gist of what P vs NP means. And this is why it's such a huge deal - the problem is almost self-referential in nature.

View on HN

> This is, after all, the gist of what P vs NP means. And this is why it's such a huge deal - the problem is almost self-referential in nature.

Could you back that up with some citations? This doesn't ring true. But my pure CS has withered a bit...

For example, algorithm that just copies it's input to output, unless input is proof of inconsistency of arithmetic, is correct algorithm to calculate function f(x) = x - yet it's unprovable in PA that it's correct.

Reply on news.ycombinator.com