Hacker News Reader

Comment by gchpaco | Hacker News Reader

There are only two "natural" problem classes known that are not either definitely in P or definitely in NP, and this article concerns one of them. (The other is integer factorization / discrete logs). And I'm not sure anybody believes there are any natural problems that are inherently in this in between state.

View on HN

The thing is though -- at the very least they could be honest and clear about this just being the state of affairs, not being something more fundamental (if it isn't believed to be). I (and I'm sure you) see over and over again so many people (probably including myself at some point) who end up being left with the impression that graph isomorphism and factorization are NP-hard, because (a) they hear those problems are hard, and (b) they're told the polynomials are the easy problems, and (c) the only non-polynomial algorithms they've ever seen are exponential-time.

(Btw, I think you mean neither definitely P nor definitely NP-hard.)

> who end up being left with the impression that graph isomorphism and factorization are NP-hard, because (a) they hear those problems are hard, and (b) they're told the polynomials are the easy problems, and (c) the only non-polynomial algorithms they've ever seen are exponential-time.

In a decent textbook on computational complexity theory, you can read that a problem is NP-hard if for every problem in NP there exists a polynomial-time reduction to it. Nobody claims that such a reduction exists, e.g. for integer factorization and graph isomorphism.

Reply on news.ycombinator.com