Studies of counting complexity classes via sets with small density
この論文にアクセスする
この論文をさがす
著者
書誌事項
- タイトル
-
Studies of counting complexity classes via sets with small density
- 著者名
-
荻原, 光徳
- 著者別名
-
オギハラ, ミツノリ
- 学位授与大学
-
東京工業大学
- 取得学位
-
博士 (理学)
- 学位授与番号
-
乙第2434号
- 学位授与年月日
-
1993-02-28
注記・抄録
博士論文
目次
- 論文目録 / (0002.jp2)
- Contents / p4 (0005.jp2)
- 1 Introduction / p1 (0006.jp2)
- 2 Preliminaries / p4 (0008.jp2)
- 2.1 Strings,Sets and Functions / p4 (0008.jp2)
- 2.2 Model of Computations / p6 (0009.jp2)
- 2.3 Complexity Classes / p8 (0010.jp2)
- 2.4 Reducibilities / p13 (0012.jp2)
- 3 Bounded Truth-Table Reducibilities to Sparse Sets / p17 (0014.jp2)
- 3.1 An Overview / p17 (0014.jp2)
- 3.2 One Word-Decreasing Self-Reducible Sets / p20 (0016.jp2)
- 3.3 The Main Technical Theorems / p33 (0022.jp2)
- 3.4 Consequences / p48 (0030.jp2)
- 4 Turing Reducibilities to Sparse Sets / p52 (0032.jp2)
- 4.1 An Overview / p52 (0032.jp2)
- 4.2 Sparse Turing Hard Sets for Counting Classes / p54 (0033.jp2)
- 4.3 Consequences / p59 (0035.jp2)
- 5 Complexity of Sparse Sets in Counting Classes / p62 (0037.jp2)
- 5.1 Counting Complexity Classes with a Special Property / p62 (0037.jp2)
- 5.2 Recognizing Sparse Sets in Counting Complexity Classes / p64 (0038.jp2)
- 6 Conclusions / p68 (0040.jp2)