通信複雑性

切り分けても切り分けても長方形

前の記事: http://azapen6.hatenablog.com/entry/2012/12/29/053705今回は引き続いて、乱数を使わないで完全なチェックを求める限りは、どうやっても対象のデータをそのまま送信するのと通信量の意味で差をつけられないことの証明に入ります。前回の最後に…

不可能の証明は用意周到に

今回と次回の話では,前回掲げた「妥協するのも悪くない」という主張の裏をとって,「妥協しないとお手上げ」という場合が実際にあることを示します。問題は前回に引き続き,アリスとボブがそれぞれ巨大なデータのコピーを持っていて,それらが完全に一致し…

アリスとボブは妥協する

本ブログの最初の記事は,「何かを計算するとき,ちょっと妥協すると大きな効果が得られる」ことがあるという話です。例えば,「ごく稀に間違った答えを出しても構わない」とか「本当に欲しい答えから少しくらいずれても構わない」といった具合です。ここで…