Re:A Solution of the P versus NP Problem?
by Sharlin on Monday August 14, 2017 @05:13PM
(#15012969)
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.
[ Parent
| on HN ]
Re:A Solution of the P versus NP Problem?
by anarazel on Monday August 14, 2017 @05:24PM
(#15013066)
> 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.