Re:Graph Isomorphism Strikes Back
by moyix on Friday January 06, 2017 @12:28PM
(#13338188)
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.
[ Parent
| on HN ]
There are no comments on this comment yet.