NP problems look like they are suitable for use as trapdoor functions or proofs of work, since they are difficult to solve, but easy to verify. Unfortunately, they seem a little hard to use in adversarial settings where an opponent can control problem selection because while worst-case problems are NP, particular instances can be solved very quickly.
So: is there any algorithm which can take instances and estimate - more efficiently than trying to solve them - how hard or close to worst-case they are?
(The context is musing about a Bitcoin protocol where the proofs-of-work were reusable and not useless hash checks. The obvious approach is to have a central authority issue, for each transaction block, a NP instance which corresponds to a real-world problem. But the central authority could be subverted, and start issuing easy problems which would render the network vulnerable to double-spends. One could accept problems from multiple authorities, or anyone, but the chosen-easy problem remains. If there were some way to estimate the difficulty of any problem presented to the network, then 'too easy' problems could simply be ignored, falling back to the hash race if necessary.)
EDIT: jaxtr links me to "Predicting Satisfiability at the Phase Transition", which gives algorithms which estimate hardness at 70% accuracy - but they don't seem to investigate whether the algorithm can be deliberately fooled. (As well, one can apparently generate SAT problems with specified probabilities of being satisfiable.)
