Computational complexity of counting complexity classes 数え上げ問題の計算量クラスの計算複雑さ

この論文をさがす

著者

    • 戸田, 誠之助, 1959- トダ, セイノスケ

書誌事項

タイトル

Computational complexity of counting complexity classes

タイトル別名

数え上げ問題の計算量クラスの計算複雑さ

著者名

戸田, 誠之助, 1959-

著者別名

トダ, セイノスケ

学位授与大学

東京工業大学

取得学位

理学博士

学位授与番号

乙第2226号

学位授与年月日

1991-06-30

注記・抄録

博士論文

目次

  1. 論文目録 / (0002.jp2)
  2. Contents / p1 (0003.jp2)
  3. 1 Introduction. / p1 (0009.jp2)
  4. 1.1 Complexity Theory and Complexity Classes / p1 (0009.jp2)
  5. 1.2 An Overview of Counting Classes / p3 (0011.jp2)
  6. 1.3 Questions and Earlier Works on Counting Classes / p5 (0013.jp2)
  7. 1.4 Outline of this thesis / p11 (0019.jp2)
  8. 1.5 Summary and Related Papers / p18 (0026.jp2)
  9. 2 Preliminaries. / p21 (0029.jp2)
  10. 2.1 Strings, sets, and functions / p21 (0029.jp2)
  11. 2.2 Model of computations / p22 (0030.jp2)
  12. 2.3 Complexity classes / p23 (0031.jp2)
  13. 2.4 Operators / p25 (0033.jp2)
  14. 2.5 Reducibilities / p26 (0034.jp2)
  15. 3 The computational difficulty of the class PP. / p29 (0037.jp2)
  16. 3.1 Basic properties of BP-complexity classes / p29 (0037.jp2)
  17. 3.2 Some properties and computational difficulty of ⊕P / p35 (0043.jp2)
  18. 3.3 Fundamental results in probabilistic polynomial time / p40 (0048.jp2)
  19. 3.4 Review of the previous results and their proof techniques / p50 (0058.jp2)
  20. 3.5 [数式]-hardness of PP for PH / p58 (0066.jp2)
  21. 4 Further Relationships between PH and counting classes. / p63 (0071.jp2)
  22. 4.1 Structures of #P(PH) / p64 (0072.jp2)
  23. 4.2 Polynomial time 1-Turing reducibility from #P(PH) to #P / p68 (0076.jp2)
  24. 4.3 Some consequences of the last result / p73 (0081.jp2)
  25. 4.4 Relating #P(PH) with #P by randomized reductions / p77 (0085.jp2)
  26. 4.5 Randomized reductions from PH to counting classes / p85 (0093.jp2)
  27. 5 Restricted relativization and positive relativizations. / p93 (0101.jp2)
  28. 5.1 Restricted relativization of PP / p94 (0102.jp2)
  29. 5.2 Positive relativizations / p98 (0106.jp2)
  30. 6 The complexity of finding middle costs / p103 (0111.jp2)
  31. 6.1 The complexity of finding K-th values and medians / p103 (0111.jp2)
  32. 6.2 Complete problems for D#P / p109 (0117.jp2)
1アクセス

各種コード

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