Average-case Complexity

d.y.d. 23:51 06/10/19 ランダム生成
Impagliazzoの"A Personal View of Average-Case Complexity" (CoCo 1995, ps file) とかかなぁと思ってみたけどランダムなインスタンス生成の話はあんまりしてませんでした. ECCC辺りを漁れば出てくるかな? と適当な反応でお茶を濁して帰ります.
今のところNP-hardな問題でaverage-case/worst-case connectionって無かった気がするなぁ.

追記

2.1 Algorithmica

P=NPまたはNP⊆BPPな世界

2.2 Heuristica

NP問題の最悪時は解けないが, NP問題の任意のインスタンスの分布について平均時では解ける世界. (難しいインスタンスは存在するが, そのインスタンスを探すのが難しい.)

2.3 Pessiland

平均時に難しい問題が存在するが, 一方向性関数は存在しない世界. (判定は難しいけど, 逆算は楽. 暗号学者にとっては一番嫌.)

2.4 Minicrypt

一方向性関数は存在するが, 公開鍵暗号は存在しない世界.

2.5 Cryptomania

公開鍵暗号が存在する世界.

HeuristicaかPessilandの辺りでインスタンス生成の話をやっていたような覚えがある.

さらに追記
自分が何を勘違いしてたか覚えてませんけど、どう考えてもインスタンス生成とかMCMCとか、そっちの話ですよね。