Hacker News Reader

Comment by memkit | Hacker News Reader

Your last statement is misleading. A problem being NP-complete isn't exactly the property that allows you to reduce any NP problem to it. Suppose there was a complexity class MP-hard that has no efficient reduction to an NP-complete problem. Then a problem being MP isn't what allows me to write a reduction to the MP-hard problem; I could just as easily write a reduction from a problem in P to the MP-hard problem. Your statement is misleading but incidentally correct because the true condition (NP-hard or easier) happens to be equivalent to your stated condition (NP) for this particular complexity class. It would be clearer to simply state that you can always reduce an easy problem to a harder one.

View on HN

What?

Being in NP doesn't exclude being in P. Every problem in P is also in NP.

The definition of "NP-complete" is "in NP, and also NP-hard". The definition of "NP-hard" is that you can reduce any NP problem to it using a poly-time mapping reduction (also known as a Karp reduction). So yes, SAT being NP-complete does mean that you can reduce any NP problem to SAT, using a poly-time mapping reduction.

Breaking a hash (e.g. collision finding) is in NP, because you can easily check a proposed solution. Well, with an obvious quibble: P and NP are about asymptotic complexity, but most hash functions are fixed-size. Also if you're looking at complexity theory you might want to talk about targeted collision finding, or first or second preimage resistance, but same deal there. But anyway, supposing you choose a keyed hash that does scale so that you can talk about its asymptotic complexity at all, and has a poly-time cost to evaluate it, breaking that hash would be in NP. Therefore it can be reduced to SAT using a poly-time mapping reduction.

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.

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.

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.

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

Reply on news.ycombinator.com