博士

ロボ子、今日は鳩の巣原理について話すのじゃ！

ロボ子

鳩の巣原理、ですか？確か、もし鳩の数より巣の数が少なければ、少なくとも一つの巣には複数の鳩が入る、というものですよね。

博士

その通り！例えば、6羽の鳩が5つの巣に入ると、必ず2羽は同じ巣に入るのじゃ。単純じゃけど、計算機科学では強力なツールになるんじゃぞ。

ロボ子

なるほど。記事では、3万人の観客がいるサッカー場で、4桁の暗証番号が同じ人が必ずいる、という例が挙げられていましたね。

博士

そうそう！これは鳩の巣原理の応用じゃ。でも、この原理を使った証明は、存在することを示すだけで、具体的な解を見つける方法は教えてくれないのじゃ。

ロボ子

非構成的な証明、というやつですね。パパディミトリウさんたちが、鳩の巣原理のようなもので存在が保証されるものを探す問題群を研究した、と。

博士

さすがロボ子、よく知っておるの！そして、今回の重要なポイントは「空の鳩の巣原理」じゃ！

ロボ子

空の鳩の巣原理、ですか？鳩の数より巣の数が多い場合、必ず空の巣が存在する、というものですよね。

博士

そうじゃ！3000席のコンサートホールで、4桁の暗証番号のうち使われていないものが必ず存在する、という例が記事にあったのじゃ。

ロボ子

確かに。でも、特定の暗証番号が使われていないことを確認するには、全員に確認する必要があるから大変ですね。

博士

そこがミソなのじゃ！そして、APEPP (abundant polynomial empty-pigeonhole principle)！鳩の巣が鳩よりもはるかに多い問題のクラスなのじゃ！

ロボ子

APEPP…なんだか呪文みたいですね。クロード・シャノンの証明に着想を得た、と。

博士

そう！ほとんどの計算問題は本質的に解きにくい、というシャノンの考えじゃ。APEPPは、計算の困難さを証明すること自体の難しさを分析する新しい方法を提供するのじゃ。

ロボ子

オリバー・コルテンさんが、難解な計算問題の探索がAPEPPの他のすべての問題と密接に関連していることを証明したんですね。

博士

その通り！コルテンさんの論文を基に、計算の困難さとランダム性との関連性に関する新たな成果が生まれているらしいぞ！

ロボ子

なるほど。鳩の巣原理から、計算問題の難しさまで繋がるとは、面白いですね。

博士

じゃろ？ところでロボ子、もしロボ子が100個のネジを持っていて、それを99個の箱に入れるとしたらどうなる？

ロボ子

えっと…少なくとも一つの箱には2個以上のネジが入りますね。鳩の巣原理的に。

博士

正解！そして、そのネジはきっと…

ロボ子

きっと…どうなるんですか？

博士

ネジだけに、外れる！…って、オチが弱かったかのじゃ？