Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

Is cryptographic hash inversion (believed to be) NP-complete, or NP-hard, etc.?

• I can't find the answer through googling, so here goes: I would think that attacking (finding a pre-image of) a hash digest would be NP complete in one sense: it's easy to very a hash inversion (putting it in NP), but difficult to find that pre-image.  This is because, for a digest of n bits, it takes exp(n) guesses to invert, making it as hard as other NP-complete problems. On the other hand, I never see it in lists of NP-complete problems: http://en.wikipedia.org/wiki/List_of_NP-complete_problems There is the possibility that it's NP-hard, which (I think) would mean that NP-complete problems can be reduced to it, but not vice versa (i.e., an oracle for hash inversion would speed up the problem of solving NP-complete problems but not vice versa), as suggested by this Euler diagram (focusing on the P != NP case here): http://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg Thoughts? UPDATE: Per : I realize that any specific cryptographic hash function has a fixed-size search space, even if it is infeasibly large (and across unbroken cryptographic hash functions in general, the inversion difficulty varies exponentially with digest length) .  So I suggest the following revision to my question to better capture what I'm asking: 1) Say there's a family of cryptographic hash functions for which you can set a parameter that determines the digest length n, which can be arbitrary large.  In that case, it's clear that the difficulty of hash inversion scales exponentially with n, and (I think) makes it at least as hard as the hardest problems in NP. In that case, would there be a reduction (in any direction) between (variable-digest-length) hash inversion and NP-complete problems? 2) Alternatively, make the comparison between a specific cryptographic hash function and a fixed-length version of an NP-complete problem.  Is there a reduction (in either direction) between the two problems?  If you had an oracle for SHA-256 inversion, for instance, would that help you solve a version of the 3-SAT problem with an upper-bounded number of clauses (for some upper bound)?

• Answer:

  You have a few misunderstandings in your question. Hash inversion cannot be in NP or NP-hard because it is not a decision problem. This is a minor technical point with a simple fix, just ask the related decision, given a hash function [math]h[/math], "For integers [math]y, d[/math], does there exist [math]x < d[/math] such that [math]h(x) = y[/math]?" If hash inversion is in NP, then it reduces to all NP-hard problems. If it is NP-hard, then all problems in NP reduce to it. The answer to this question depends entirely upon what your hashing function is. If your hashing function hashes all messages to the same number of bits (as almost all hash functions do), then the answer is trivially no, your inverting the hash function is not NP-hard (unless P = NP). In that case there are only a finite number of inputs (outputs of the hash function), so I can hard code the answer for all of them and then look up the answer in linear time. There are probably some hash functions for which hash inversion is NP-hard, simply because there are lots of functions. I am not aware of any though. All that said, NP-hardness is a pretty useless property for hash inversion to have. Hash functions are thought to be one-way functions*, functions for which it is easy to evaluate them and hard to invert them on most inputs**. This is the critical distinction between inverting one-way functions and NP-hard problems. NP-hard problems only have to be hard to solve on some inputs. Knowing that a problem is NP-hard tells you almost nothing about whether it can be used to make a one-way function. * One-way functions are not known to actually exist. Even if P [math]\ne[/math] NP, they are not know to exist. ** Formally, a function [math]f[/math] is one-way if for every polynomial, randomized algorithm [math]A[/math], every polynomial [math]p[/math], and all sufficiently large [math]n[/math], [math]Pr[f(A(f(x))) = f(x)] < 1 / p(n)[/math] where [math]x[/math] is chosen uniformly from [math]\{0,1\}^n[/math].