Hacker News Reader

Moreover, most hard problems are simply proven hard because they incorporate a hard problem.

Eg. Many proofs that say "this problem is NP-Hard" just prove that "you would have to solve xyz NP-Hard problem to solve this"

View on HN

NP-Hardness proofs don't say "you would have to solve xyz NP-Hard problem to solve this", they say "if you could solve the problem you're interested in, you could use the solution to solve all other NP-complete problems". It's not that they incorporate a hard problem -- rather, you show that your problem is hard enough that it can be used to solve other hard problems.

I'm not clear what you mean -- how else would you prove a problem NP-hard in general? That's usually the most sensible way.

Reply on news.ycombinator.com