Some nonlinear lower bounds on the size of restricted circuits of boolean functions 制限付き回路で論理関数を計算する場合の回路の大きさに関する非線形下限について
この論文にアクセスする
この論文をさがす
著者
書誌事項
- タイトル
-
Some nonlinear lower bounds on the size of restricted circuits of boolean functions
- タイトル別名
-
制限付き回路で論理関数を計算する場合の回路の大きさに関する非線形下限について
- 著者名
-
築地, 立家
- 著者別名
-
ツキジ, タツイエ
- 学位授与大学
-
東京工業大学
- 取得学位
-
博士 (工学)
- 学位授与番号
-
甲第3562号
- 学位授与年月日
-
1997-03-26
注記・抄録
博士論文
目次
- 論文目録 / (0002.jp2)
- Contents / p1 (0004.jp2)
- 1 Introduction / p1 (0007.jp2)
- 1.1 Short Preliminaries / p5 (0009.jp2)
- 2 Boolean Sums / p7 (0010.jp2)
- 2.1 Monotone Complexity of Boolean Sums / p7 (0010.jp2)
- 2.2 Sketch of the Proof / p9 (0011.jp2)
- 2.3 Proof of Theorem 2.4 / p12 (0012.jp2)
- 3 Monotone and Nonmonotone Circuit Complexity / p17 (0015.jp2)
- 3.1 Examples that Monotone and Nonmonotote Circuit Complexity Coincide / p17 (0015.jp2)
- 3.2 Takeuti's Program / p17 (0015.jp2)
- 3.3 Gate Elimination Technique / p18 (0015.jp2)
- 3.4 2n circuit size lower bound of a projection of F₂n / p19 (0016.jp2)
- 4 Set Systems / p23 (0018.jp2)
- 4.1 Complexity of Set Systems / p23 (0018.jp2)
- 4.2 Incremental Circuits / p24 (0018.jp2)
- 4.3 Disjoint Circuits / p27 (0020.jp2)
- 5 Boolean Shifter / p33 (0023.jp2)
- 5.1 Introduction and Definition / p33 (0023.jp2)
- 5.2 Input-wise Synchronous Boolean Shifter / p35 (0024.jp2)
- 5.3 Treelike Boolean Shifter / p36 (0024.jp2)
- 6 The Depth of Random Circuits / p39 (0026.jp2)
- 6.1 The Problem and Motivation / p39 (0026.jp2)
- 6.2 Proof Outline,Definitions and Notations / p40 (0026.jp2)
- 6.3 Domination by Coupling / p42 (0027.jp2)
- 6.4 The Depth of Circuits / p44 (0028.jp2)