>ah, that's why we couldn't solve that -- because we proved it is in NP, and P isn't equal to that, so we can chalk our failure to solve it up to that. Except

>ah, that's why we couldn't solve that -- because we proved it is in NP, and P isn't equal to that, so we can chalk our failure to solve it up to that. Except that line of reasoning is completely incorrect -- both in its understanding of the problem, and in its understanding of the current state of the field. For one, most "interesting" problems are in NP, not the least of reasons being P is undeniably a subset of NP. Here's a nice Venn-diagram-like thing on wikipedia: https://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg https://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.... So if you prove your solution is NP, you don't get to say "Whelp, it's impossible!" and move on. That would be like saying "We proved that you could build this machine if we had a perpetual motion engine, and those are probably impossible, so the machine can't be built." If, on the other hand, you prove that your machine could be used to build a "perpetual motion engine" (i.e. a poly-time solution to the new problem could be used to construct a poly-time solution to an NP-complete problem), then that might be a good time to admit it's almost certainly impossible to build it. But again, that's not where the field lets it rest. NP-complete problems have very direct applications to many, many real world problems we try to solve. The state of the art in these solutions is not "It will never be polynomial time, so we don't try." Research papers are constantly churning out new, faster algorithms for NP-complete problems -- they're just not poly-time algorithms. For example, k-sat is the most textbook example of an NP-complete problem, and there is an annual competition regarding the latest algorithms for solving it: http://www.satcompetition.org/ http://www.satcompetition.org/ In fact, working on this stuff isn't exactly the smallest field within CS, and a novel solution yielding better performance does very well to an academic reputation, and there are definitely people trying. So rest assured, in the unlikely event that some new techniques arise that allow the creation of poly-time solutions to NP-complete problems, they will not go unnoticed. But thanks for calling us cowards.