# Why Can't Reverse Hashing Prove $P \neq NP$?

Lets assume a hashing algorithm that runs in polynomial time and produces a hash that is mathematically impossible to reverse. As far as I know, the $P=NP$ problem states that if they are indeed equal, then if an algorithm exists to verify a solution in polynomial time, then an algorithm exists to find a solution in polynomial time. In this case, we can verify a solution by just running it through the hashing algorithm and comparing the final results. However, there cannot exist an algorithm to find a solution, since the hash is impossible to reverse.

• Define "mathematically impossible to reverse". There are multiple possible meanings of that. You might want to read about one-way functions and cryptographically secure hash functions.
– D.W.
Dec 15, 2017 at 3:00
• @D.W. Sorry, I meant a one-way hash function. To my understanding, these are impossible to reverse since they rely on numerous other one-way mathematical operations. Or are they actually possible to reverse and it's just extremely difficult to do so? Dec 15, 2017 at 3:10
• That understanding is incorrect. Consider the algorithm that tries all possible inputs of the right length and hashes each of them to see which produces the right output.
– D.W.
Dec 15, 2017 at 15:30

That’s an open problem. It can’t currently be used to resolve $P$ vs $NP$ because no one knows if there is an example of such a function. In CS, we often assume that $P\neq NP$ and that there are cryptographically secure hashes, but that’s an (experienced based) assumption, not a probable fact.
• Thank you for the reply. I figured that if there exists a hashing algorithm that is impossible to reverse, and that runs in polynomial time, that would lead us to conclude that $P\neq NP$, because you would have a solution that can be verified in polynomial time, but it would be impossible to come up with a solution from just the hash. Dec 15, 2017 at 5:28