Studies of counting complexity classes via sets with small density
Access this Article
Search this Article
Author
Bibliographic Information
- Title
-
Studies of counting complexity classes via sets with small density
- Author
-
荻原, 光徳
- Author(Another name)
-
オギハラ, ミツノリ
- University
-
東京工業大学
- Types of degree
-
博士 (理学)
- Grant ID
-
乙第2434号
- Degree year
-
1993-02-28
Note and Description
博士論文
Table of Contents
- 論文目録 / (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)