Assessing the complexity of cases of NP problems

Question

NP problems appear to be suitable for use as hatch functions or proof of work, as they are difficult to solve but easy to verify. Unfortunately, they seem a little difficult to use in competitive situations where the adversary can control the choice of a problem, because while the worst problems are NP, specific cases can be solved very quickly.

So: is there any algorithm that can take instances and evaluate - more efficiently than trying to solve them - how difficult or close to worse are they?

(The context reflects on the Bitcoin protocol, where evidence of work can be reused, rather than useless hash checks. The obvious approach is to have central authority for each block of transactions, an NP instance that matches the real problem, but central authority can be undermined and start to issue simple problems that would make the network vulnerable to double spending.You could accept problems from several authorities or someone, but the problem with the chosen-easy one remains. were somehow appreciate the complexity of any problem presented to the network, while "too simple" problems could simply be ignored, if necessary, return to the race hashes, if necessary.)

EDIT: jaxtr connects me with “Prediction of Satisfactory Phase Transition,” which gives algorithms that evaluate hardness with an accuracy of 70% - but they don't seem to be studying whether the algorithm can be deliberately misled. (In addition, you can apparently generate SAT problems with certain execution probabilities.)

Answer 1

This is the same problem faced by researchers trying to create np-based public key encryption algorithms. As far as I know, there are some hits in it, but this is still a problem. See Discussion here: Are there public-key cryptographic algorithms that are apparently NP-hard to beat?

I know that I saw a later work, but I can not find it. I recall a book consisting of articles on alternative cryptosystems if factorization suddenly becomes cheap and I try to dig out a link.

Change The comment below points to the book I was thinking about. There are many good links on the website to various related documents. See Code Based Section.