[alexbecker]

It's worth pointing out that while modern hash functions are believed to be infeasible to unscramble (technically, to require exponential time), none have been proven so. In fact, proving the mere existence of such a function would prove P!=NP.

[fiddlerwoaroof]

Wouldn’t it prove the opposite namely that P equals NP?

[Thorrez]

No, if you can prove that a secure hash function exists, then you have proved that P != NP. (This is what alexbecker said.)

If you can prove P = NP, then you have proved that no secure hash functions exist. (This is the contrapositive.)

[repsilat]

For convenient definitions of "secure" :-). "Unscrambling" a particular function could be in P but still effectively intractable.

(For a fun angle not related to complexity, the algorithm itself could be so large that it wouldn't fit in the observable universe without breaking the Bekenstein bound.)

And it has been a long time since I did proof theory, but is there the possibility of a non-constructive proof but no actual examples no matter how long you keep enumerating algorithms? Or a non-constructive proof, but no constructive proof? In that case there could be a "perfect heuristic"...

[fiddlerwoaroof]

Oops, this is what I get for not reading carefully :) But this is interesting: it implies, if I'm not mistaken, it implies that we haven't ever proven that a function takes exponential time, just that we haven't found any algorithms for certain problems faster than exponential time. I hadn't considered P != NP this way before...

[gpm]

No, we know that P != EXP_TIME, by the time hierarchy theorem - i.e. we know some problems (and we do have concrete examples) take exponential time. What we don't know is that there exists a problem that requires exponential time (or otherwise greater than polynomial) where we can create a proof that a answer is correct which is checkable in polynomial time.

https://en.wikipedia.org/wiki/Time_hierarchy_theorem

[w8rbt]

I think you mean... P = NP. Which is very unlikely as we could do away with mathematicians if that were true.

[jrochkind1]

Seems unlikely, but not proven. That's the point. I dunno about 'do away with mathematicians'.

[fiddlerwoaroof]

Yeah, I just thought that showing how to solve a best-case exponential function in polynomial kind was the sort of thing that would prove P = NP (I dictated this before, so NP came out as MP)