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

注記・抄録

博士論文

目次

  1. 論文目録 / (0002.jp2)
  2. Contents / p1 (0004.jp2)
  3. 1 Introduction / p1 (0007.jp2)
  4. 1.1 Short Preliminaries / p5 (0009.jp2)
  5. 2 Boolean Sums / p7 (0010.jp2)
  6. 2.1 Monotone Complexity of Boolean Sums / p7 (0010.jp2)
  7. 2.2 Sketch of the Proof / p9 (0011.jp2)
  8. 2.3 Proof of Theorem 2.4 / p12 (0012.jp2)
  9. 3 Monotone and Nonmonotone Circuit Complexity / p17 (0015.jp2)
  10. 3.1 Examples that Monotone and Nonmonotote Circuit Complexity Coincide / p17 (0015.jp2)
  11. 3.2 Takeuti's Program / p17 (0015.jp2)
  12. 3.3 Gate Elimination Technique / p18 (0015.jp2)
  13. 3.4 2n circuit size lower bound of a projection of F₂n / p19 (0016.jp2)
  14. 4 Set Systems / p23 (0018.jp2)
  15. 4.1 Complexity of Set Systems / p23 (0018.jp2)
  16. 4.2 Incremental Circuits / p24 (0018.jp2)
  17. 4.3 Disjoint Circuits / p27 (0020.jp2)
  18. 5 Boolean Shifter / p33 (0023.jp2)
  19. 5.1 Introduction and Definition / p33 (0023.jp2)
  20. 5.2 Input-wise Synchronous Boolean Shifter / p35 (0024.jp2)
  21. 5.3 Treelike Boolean Shifter / p36 (0024.jp2)
  22. 6 The Depth of Random Circuits / p39 (0026.jp2)
  23. 6.1 The Problem and Motivation / p39 (0026.jp2)
  24. 6.2 Proof Outline,Definitions and Notations / p40 (0026.jp2)
  25. 6.3 Domination by Coupling / p42 (0027.jp2)
  26. 6.4 The Depth of Circuits / p44 (0028.jp2)
0アクセス

各種コード

  • NII論文ID(NAID)
    500000153764
  • NII著者ID(NRID)
    • 8000001092778
  • DOI(NDL)
  • NDL書誌ID
    • 000000318078
  • データ提供元
    • NDL-OPAC
    • NDLデジタルコレクション
ページトップへ