HNHacker News
TopNewBestAskShowJobs

drak3

19 karma · joined August 24, 2016

submissionscomments
drak3··on The Imposter's Handbook
The excerpt on the Boolean Satisfiability Problem reads

> The basic concept that people have figured out, so far, is that a number of NP-complete problems can likely be solved if we crack the Boolean Satisfiability problem.

And

> If NP-Complete problems get resolved, it is likely (though nobody knows for sure) that we'll crack every NP-Problem

Isn't the definition of a NP-Complete problem exactly that it is in NP _and_ every other problem in NP can be reduced to it in polynomial time. So we know _for sure_ ([Cook71]), that as soon we have a polynomial algorithm for SAT _every_ problem in NP can be solved in polynomial time, and not just some of them as the excerpt claims.

Am I missing something? Because this seems like a very confusing, if not downright wrong, way to explain NP-completeness and its link to SAT.

[Cook71] Cook, S.A. (1971). "The complexity of theorem proving procedures". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. pp. 151–158.