20/02/15 23:12:20.49 tI+VIYb9.net
メモ
これ（下記）の付録が分り易い
連続体仮説の解説がいいね
URLﾘﾝｸ(tokyo-metro-u.repo.nii.ac.jp)
PDF URLﾘﾝｸ(tokyo-metro-u.repo.nii.ac.jp)
完全二分AND-OR 木に対する最適乱択アルゴリズムの特徴づけと木転置グラフの構造について
アイテムタイプ 学位論文 / Thesis or Dissertation
言語 日本語
著者 小川 孝典
著者(ヨミ) オガワ コウスケ
著者別名 Ogawa Kousuke
抄録 計算複雑さの理論の一分野として, AND-OR 木の研究がある.
我々は, randomized complexity を達成する乱択アルゴリズムを最適乱択アルゴ
リズムとよび, i-セット(i 2 f0; 1g) に対してコスト期待値が一定の乱択アルゴリズ
ムをEi-乱択アルゴリズムと定義する. 本論文では, 連結閉集合上の乱択アルゴリズ
ムについて, i-セットに対して最適であることとEi であることが同値であることを
証明する. これは, 鈴木-中村[SuNa] の結果の双対的な結果とみなすことができる.
また, 真理値割り当てからなる集合にグラフの構造を入れ、木の高さに関する構造
定理を示す.
付録として, 無限組み合わせ論におけるdiamond principle に関連したhitting
principle についての考察を加える. hitting principle をP へ持ち上げ, P に
おけるdiamond principle との関連づけを与える.
内容記述 首都大学東京, 2013-03-25, 修士（理学）
ページ 1 - 50
発行年 2013-03-25