NP 問題は、解決するのが難しいが、検証するのは簡単であるため、落し戸関数またはプルーフ オブ ワークとしての使用に適しているように見えます。残念ながら、対戦相手が問題の選択をコントロールできる敵対的な設定では、それらを使用するのは少し難しいように見えます。これは、最悪の場合の問題は NP ですが、特定のインスタンスは非常に迅速に解決できるためです。
だから：インスタンスを取り、それらを解決しようとするよりも効率的に推定できるアルゴリズムはありますか？
(コンテキストは、プルーフ・オブ・ワークが再利用可能で、役に立たないハッシュ・チェックではないビットコイン・プロトコルについて熟考しています。明らかなアプローチは、トランザクション・ブロックごとに、実世界に対応する NP インスタンスを中央機関の問題にすることです。問題. しかし、中央当局は転覆する可能性があります, そして、ネットワークを二重支出に対して脆弱にする簡単な問題を発行し始める可能性があります. 複数の当局または誰からの問題も受け入れることができますが、選択された簡単な問題は残ります.ネットワークに提示された問題の難しさを推定するために、「簡単すぎる」問題は単純に無視して、必要に応じてハッシュ レースに戻すことができます。)
編集: jaxtr は、70% の精度で硬度を推定するアルゴリズムを提供する"Predicting Satisfiability at the Phase Transition"にリンクしていますが、アルゴリズムが故意にだまされる可能性があるかどうかを調査していないようです。(同様に、特定の確率で充足可能である SAT 問題を明らかに生成することもできます。)