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.
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"...
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...
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.
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)
