3 ms·
Breaking polynomially computable hashes is in NP, in the sense that its decision version - is there any word lexicographicaly smaller than w that hashes out to
by xxxyy 12y ago
Breaking polynomially computable hashes is in NP, in the sense that its decision version - is there any word lexicographicaly smaller than w that hashes out to v - is in the NP class. Thus P=NP would give us a procedure to compute preimages of all known reasonable hash functions, with complexity depending on the size of the shortest solution.
- j2kun 12y agoThat is one implication. But as I explained in my other comment, the nonexistence of one-way functions does not imply the resolution of P versus NP. So the two problems are not equivalent.