NP 问题看起来适合用作陷门函数或工作证明，因为它们难以解决，但易于验证。不幸的是，在对手可以控制问题选择的对抗环境中，它们似乎有点难以使用，因为虽然最坏情况问题是 NP，但可以非常快速地解决特定情况。
那么：是否有任何算法可以采用实例并估计 - 比尝试解决它们更有效 - 它们有多难或接近最坏情况？
（上下文在思考一个比特币协议，其中工作证明是可重用的，而不是无用的哈希检查。显而易见的方法是有一个中央权威问题，对于每个交易块，一个对应于现实世界的 NP 实例问题。但是中央权威可能会被颠覆，并开始发布简单的问题，这会使网络容易受到双重支出的影响。一个人可以接受来自多个权威或任何人的问题，但选择的简单问题仍然存在。如果有某种方法估计任何呈现给网络的问题的难度，那么“太容易”的问题可以简单地忽略，必要时退回到哈希竞赛。）
编辑：jaxtr 将我链接到“Predicting Satisfiability at the Phase Transition”，它提供了以 70% 的准确度估计硬度的算法 - 但他们似乎没有调查该算法是否可以被故意愚弄。（同样，显然可以产生具有特定概率可满足性的 SAT 问题。）