Studies of counting complexity classes via sets with small density

この論文をさがす

著者

    • 荻原, 光徳 オギハラ, ミツノリ

書誌事項

タイトル

Studies of counting complexity classes via sets with small density

著者名

荻原, 光徳

著者別名

オギハラ, ミツノリ

学位授与大学

東京工業大学

取得学位

博士 (理学)

学位授与番号

乙第2434号

学位授与年月日

1993-02-28

注記・抄録

博士論文

目次

  1. 論文目録 / (0002.jp2)
  2. Contents / p4 (0005.jp2)
  3. 1 Introduction / p1 (0006.jp2)
  4. 2 Preliminaries / p4 (0008.jp2)
  5. 2.1 Strings,Sets and Functions / p4 (0008.jp2)
  6. 2.2 Model of Computations / p6 (0009.jp2)
  7. 2.3 Complexity Classes / p8 (0010.jp2)
  8. 2.4 Reducibilities / p13 (0012.jp2)
  9. 3 Bounded Truth-Table Reducibilities to Sparse Sets / p17 (0014.jp2)
  10. 3.1 An Overview / p17 (0014.jp2)
  11. 3.2 One Word-Decreasing Self-Reducible Sets / p20 (0016.jp2)
  12. 3.3 The Main Technical Theorems / p33 (0022.jp2)
  13. 3.4 Consequences / p48 (0030.jp2)
  14. 4 Turing Reducibilities to Sparse Sets / p52 (0032.jp2)
  15. 4.1 An Overview / p52 (0032.jp2)
  16. 4.2 Sparse Turing Hard Sets for Counting Classes / p54 (0033.jp2)
  17. 4.3 Consequences / p59 (0035.jp2)
  18. 5 Complexity of Sparse Sets in Counting Classes / p62 (0037.jp2)
  19. 5.1 Counting Complexity Classes with a Special Property / p62 (0037.jp2)
  20. 5.2 Recognizing Sparse Sets in Counting Complexity Classes / p64 (0038.jp2)
  21. 6 Conclusions / p68 (0040.jp2)
0アクセス

各種コード

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