complexity-theory - 估计 NP 问题实例的难度

Question

NP 问题看起来适合用作陷门函数或工作证明，因为它们难以解决，但易于验证。不幸的是，在对手可以控制问题选择的对抗性环境中，它们似乎有点难以使用，因为虽然最坏情况问题是 NP，但可以非常快速地解决特定情况。

那么:是否有任何算法可以采用实例和估计 - 比尝试解决它们更有效 - 它们有多难或接近最坏情况？

(上下文在思考一个比特币协议(protocol)，其中工作证明是可重用的，而不是无用的哈希检查。显而易见的方法是有一个中央权威问题，对于每个交易 block ，一个对应于现实世界的 NP 实例问题。但是中央权威可能会被颠覆，并开始发布简单的问题，这会使网络容易受到双重支出的影响。一个人可以接受来自多个权威或任何人的问题，但选择的简单问题仍然存在。如果有某种方法估计任何呈现给网络的问题的难度，那么“太容易”的问题可以简单地忽略，必要时退回到哈希竞赛。)

编辑:jaxtr 将我链接到 "Predicting Satisfiability at the Phase Transition" ，它给出了以 70% 的准确度估计硬度的算法——但他们似乎没有调查该算法是否可以被故意愚弄。 (同样，显然可以产生具有特定概率可满足性的 SAT 问题。)

Answer 1

这与试图创建基于 np 完整性的公钥加密算法的研究人员所面临的问题相同。据我所知，有一些问题，但这仍然是一个悬而未决的问题。请参阅此处的讨论:Are there public key cryptography algorithms that are provably NP-hard to defeat?

我知道我看过更多最近的作品，但不能随便找到。我记得一本由有关替代密码系统的文章组成的书应该因式分解突然变得便宜，我将尝试挖掘链接。

编辑 :下面的评论指向我正在考虑的书。 The website对各种相关论文有很多很好的引用。具体参见“基于代码”部分。