Computational complexity of boolean formulas with query symbols クエリー記号付きブール式の計算複雑さ

この論文をさがす

著者

    • 鈴木, 登志雄 スズキ, トシオ

書誌事項

タイトル

Computational complexity of boolean formulas with query symbols

タイトル別名

クエリー記号付きブール式の計算複雑さ

著者名

鈴木, 登志雄

著者別名

スズキ, トシオ

学位授与大学

筑波大学

取得学位

博士 (理学)

学位授与番号

乙第1498号

学位授与年月日

1999-03-25

注記・抄録

博士論文

目次

  1. Contents / p1 (0003.jp2)
  2. Preface / p3 (0004.jp2)
  3. Acknowledgement / p5 (0005.jp2)
  4. 1 Introduction / p1 (0006.jp2)
  5. 1.1 Forcing complexity and historical background / p1 (0006.jp2)
  6. 1.2 Motive for the study / p4 (0008.jp2)
  7. 1.3 Aim of this thesis / p6 (0009.jp2)
  8. 2 Preliminaries / p11 (0011.jp2)
  9. 2.1 Guide to this chapter / p11 (0011.jp2)
  10. 2.2 Computational complexity / p13 (0012.jp2)
  11. 2.3 Random oracles and generic oracles / p15 (0013.jp2)
  12. 2.4 The relativized propositional calculus / p17 (0014.jp2)
  13. 3 t-generic Oracles / p21 (0016.jp2)
  14. 3.1 Ceiling-generic oracles / p21 (0016.jp2)
  15. 3.2 Exponential lower bound / p23 (0017.jp2)
  16. 4 r-generic Oracles / p27 (0019.jp2)
  17. 4.1 What is difficult in the original proof? / p27 (0019.jp2)
  18. 4.2 Disentangled r-query tautologies / p29 (0020.jp2)
  19. 4.3 Hierarchy / p37 (0024.jp2)
  20. 5 Cohen-Feferman Generic Oracles / p47 (0029.jp2)
  21. 5.1 Separation of complexity classes / p47 (0029.jp2)
  22. 5.2 Examples / p50 (0031.jp2)
  23. 6 One-query versus One-question / p55 (0033.jp2)
  24. 6.1 Reducibilities / p55 (0033.jp2)
  25. 6.2 Initial segments of oracles / p56 (0034.jp2)
  26. 6.3 Disjunctive reducibility / p58 (0035.jp2)
  27. 6.4 One-question truth table reducibility / p62 (0037.jp2)
  28. 7 Control of While-loops / p67 (0039.jp2)
  29. 7.1 Problem of this chapter / p67 (0039.jp2)
  30. 7.2 Algorithm for 1-query tautologies / p68 (0040.jp2)
  31. 7.3 Algorithm for general case / p72 (0042.jp2)
  32. 7.4 Conclusion of this chapter / p78 (0045.jp2)
  33. 8 Conclusive Remark / p81 (0046.jp2)
  34. Bibliography / p83 (0047.jp2)
  35. Index / p87 (0049.jp2)
0アクセス

各種コード

  • NII論文ID(NAID)
    500000185794
  • NII著者ID(NRID)
    • 8000000186077
  • DOI(NDL)
  • NDL書誌ID
    • 000000350108
  • データ提供元
    • NDL ONLINE
    • NDLデジタルコレクション
ページトップへ