Re:Throwing some light on NP-completeness and the P=NP problem
by ck113 on Wednesday June 03, 2009 @03:42PM
(#640266)
Sure, of course. I'm not out to convince anyone that P != NP here, especially not using Proof By Obviousness. I just meant to underline one of the intuitions that makes so many people believe they must be different.
Also, like so many terms in computer science, "harder" has different meanings in different subspecialities. To a complexity theorist, a problem that takes O(n^127) time to solve is not any harder than one that takes O(n) to solve -- they're both in the same hardness class. Just one of the many warpings in perspective that staring too long at P and NP can give you.
Also, like so many terms in computer science, "harder" has different meanings in different subspecialities. To a complexity theorist, a problem that takes O(n^127) time to solve is not any harder than one that takes O(n) to solve -- they're both in the same hardness class. Just one of the many warpings in perspective that staring too long at P and NP can give you.