2008-03-20から1日間の記事一覧

Hardness Amplification

BPP の derandomization に関する Impagliazzo-Wigderson の結果が改良できたと思うのですが,まだ詳細を詰めることができていません.早めに証明を完成させねば.

講演準備

明日の中高生向けの講義の準備が一応完了しました.三時間分新たに書き下ろしたので結構大変でした.NP vs. P 予想,ゼロ知識証明,PCPの話を紹介する予定です.帰着の概念の説明に良い具体例が見つかっておらずちょっとモヤモヤですが.