[memkit]

I agree with you, I just think the condition "being in NP" is needlessly confusing. The whole point is that you can always find a reduction from easier problems to harder ones. It just so happens that NP encompasses all the problems easier than SAT.

The reason why your statement is confusing to me is that if you generalize it beyond NP, it breaks down; for an arbitrarily hard complexity class M and an arbitrary M-hard problem, you don't need to be in M to be able to find a reduction to the M-hard problem.

[less_less]

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.

[memkit]

Yes, I apologize for being combative. I see your point now.

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.

[less_less]

Ah. I didn't mean to introduce a "necessary" constraint at all, but my wording wasn't the best.