Generalised dynamic ordinals - Universal measures for implicit computational complexity

被引:0
|
作者
Beckmann, Arnold [1 ]
机构
[1] Univ Coll Swansea, Swansea SA2 8PP, W Glam, Wales
来源
Logic Colloquium '02 | 2006年 / 27卷
关键词
bounded arithmetic; dynamic ordinals; universal measures; witness oracle turing machines; implicit computational complexity; independence results; Hastad's switching lemmas; cut-reduction by switching;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We extend the definition of dynamic ordinals to generalised dynamic ordinals. We compute generalised dynamic ordinals of all fragments of relativised bounded arithmetic by utilising methods from Boolean complexity theory, similar to Krajicek in [14]. We indicate the role of generalised dynamic ordinals as universal measures for implicit computational complexity. I.e., we describe the connections between generalised dynamic ordinals and witness oracle Turing machines for bounded arithmetic theories. In particular, through the determination of generalised dynamic ordinals we re-obtain well-known independence results for relativised bounded arithmetic theories.
引用
收藏
页码:48 / 74
页数:27
相关论文
共 9 条
  • [1] A note on universal measures for weak implicit computational complexity
    Beckmann, A
    LOGIC FOR PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND REASONING, 2002, 2514 : 53 - 67
  • [2] Quantum implicit computational complexity
    Dal Lago, Ugo
    Masini, Andrea
    Zorzi, Margherita
    THEORETICAL COMPUTER SCIENCE, 2010, 411 (02) : 377 - 409
  • [4] Probabilistic Recursion Theory and Implicit Computational Complexity
    Dal Lago, Ugo
    Zuppiroli, Sara
    Gabbrielli, Maurizio
    SCIENTIFIC ANNALS OF COMPUTER SCIENCE, 2014, 24 (02) : 177 - 216
  • [5] Implicit Computational Complexity of Subrecursive Definitions and Applications to Cryptographic Proofs
    Patrick Baillot
    Gilles Barthe
    Ugo Dal Lago
    Journal of Automated Reasoning, 2019, 63 : 813 - 855
  • [6] Implicit computational complexity and the exponential time-space classes
    Caporaso, Salvatore
    Covino, Emanuele
    Gissi, Paolo
    Pani, Giovanni
    PROCEEDINGS OF THE 6TH WSEAS INTERNATIONAL CONFERENCE ON TELECOMMUNICATIONS AND INFORMATICS (TELE-INFO '07)/ 6TH WSEAS INTERNATIONAL CONFERENCE ON SIGNAL PROCESSING (SIP '07), 2007, : 65 - +
  • [7] Formally Verified Resource Bounds through Implicit Computational Complexity
    Rusch, Neea
    COMPANION PROCEEDINGS OF THE 2022 ACM SIGPLAN INTERNATIONAL CONFERENCE ON SYSTEMS, PROGRAMMING, LANGUAGES, AND APPLICATIONS: SOFTWARE FOR HUMANITY, SPLASH COMPANION 2022, 2022, : 17 - 20
  • [8] Implicit Computational Complexity of Subrecursive Definitions and Applications to Cryptographic Proofs
    Baillot, Patrick
    Barthe, Gilles
    Dal Lago, Ugo
    JOURNAL OF AUTOMATED REASONING, 2019, 63 (04) : 813 - 855
  • [9] Extending the implicit computational complexity approach to the sub-elementary time-space classes
    Covino, E
    Pani, G
    Caporaso, S
    ALGORITHMS AND COMPLEXITY, 2000, 1767 : 239 - 252