|
|
|
|
|
|
by less_less
492 days ago
|
|
|
OK, I'm sorry for the touchy response. But I still don't understand your point. Breaking a hash is a prototypical NP problem (ok maybe FNP). SAT is the prototypical NP-hard problem. I was just trying to explain that using SAT to attack hashes is therefore unsurprising, and does not in any way imply that breaking hashes is NP-complete, the way that it would if the reduction went in the other direction. Surely the same logic would make sense for another class M, if you had a problem "M-HASH" that's clearly in M, and an M-hard problem "M-SAT" to reduce it to? There might be other problems that you could also reduce to M-SAT, but mentioning that it solves all of M is what's relevant if M-HASH is in M. |
|
|
I think I'm also wrong.
I thought about my original response some more and this is a more coherent version of what I was trying to say:
A problem being in NP is sufficient but not necessary to reduce it to an NP-complete problem.
But that's wrong. It's both sufficient and necessary to be in NP. It intuitively feels like you're tacking on more than you need to by introducing the "necessary" constraint, but it makes sense.