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