4 ms·
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
by VodkaHaze 10y ago
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"
- CJefferson 10y agoI'm not clear what you mean -- how else would you prove a problem NP-hard in general? That's usually the most sensible way.
- moyix 10y agoNP-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.