ブール代数に基づいた計算の複雑さに関する研究
この論文にアクセスする
この論文をさがす
著者
書誌事項
- タイトル
-
ブール代数に基づいた計算の複雑さに関する研究
- 著者名
-
天野, 一幸
- 著者別名
-
アマノ, カズユキ
- 学位授与大学
-
東北大学
- 取得学位
-
博士 (情報科学)
- 学位授与番号
-
甲第5718号
- 学位授与年月日
-
1996-03-26
注記・抄録
博士論文
目次
- 目次 / p1 (0004.jp2)
- 1 序論 / p3 (0006.jp2)
- 1.1 本研究の背景と目的 / p3 (0006.jp2)
- 1.2 本論文の構成 / p6 (0009.jp2)
- 2 論理関数の複雑さ / p9 (0012.jp2)
- 2.1 はじめに / p9 (0012.jp2)
- 2.2 ブール代数と論理関数 / p9 (0012.jp2)
- 2.3 論理回路 / p12 (0015.jp2)
- 2.4 チューリング機械と論理回路の関係 / p14 (0017.jp2)
- 2.5 過去の結果 / p16 (0019.jp2)
- 2.6 Razborovの近似法 / p17 (0020.jp2)
- 2.7 まとめ / p21 (0024.jp2)
- 3 近似演算の一般化と否定限定論理回路 / p23 (0026.jp2)
- 3.1 はじめに / p23 (0026.jp2)
- 3.2 近似演算の一般化 / p25 (0028.jp2)
- 3.3 否定限定論理回路に対する近似法の適用 / p31 (0034.jp2)
- 3.4 まとめ / p41 (0044.jp2)
- 4 切断の概念に基づいた近似理論 / p43 (0046.jp2)
- 4.1 はじめに / p43 (0046.jp2)
- 4.2 切断の概念に基づく近似法 / p45 (0048.jp2)
- 4.3 クリーク関数の単調複雑さ / p50 (0053.jp2)
- 4.4 近似モデルの構造 / p60 (0063.jp2)
- 4.5 擬似補関数に対する近似モデル / p69 (0072.jp2)
- 4.6 非決定性論理回路に対する近似モデル / p77 (0080.jp2)
- 4.7 まとめ / p82 (0085.jp2)
- 5 k-限定独立性に基づいたDNF式の近似アルゴリズム / p84 (0087.jp2)
- 5.1 はじめに / p85 (0088.jp2)
- 5.2 k-限定独立確率分布 / p86 (0089.jp2)
- 5.3 DNF式の充足割り当ての近似数え上け / p92 (0095.jp2)
- 5.4 まとめ / p109 (0112.jp2)
- 6 結論 / p111 (0114.jp2)
- 謝辞 / p114 (0117.jp2)
- 参考文献 / p115 (0118.jp2)
- 発表論文 / p120 (0123.jp2)