Some nonlinear lower bounds on the size of restricted circuits of boolean functions 制限付き回路で論理関数を計算する場合の回路の大きさに関する非線形下限について
Access this Article
Search this Article
Author
Bibliographic Information
- Title
-
Some nonlinear lower bounds on the size of restricted circuits of boolean functions
- Other Title
-
制限付き回路で論理関数を計算する場合の回路の大きさに関する非線形下限について
- Author
-
築地, 立家
- Author(Another name)
-
ツキジ, タツイエ
- University
-
東京工業大学
- Types of degree
-
博士 (工学)
- Grant ID
-
甲第3562号
- Degree year
-
1997-03-26
Note and Description
博士論文
Table of Contents
- 論文目録 / (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)