1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Dec 15, 2017 at 3:00
  • $\begingroup$ @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? $\endgroup$
    – Badr B
    Dec 15, 2017 at 3:10
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Dec 15, 2017 at 15:30

1 Answer 1

2
$\begingroup$

Give a polynomial time hash function that takes exponential time to compute the inverse of.

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Badr B
    Dec 15, 2017 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.