Journal article 993 views
Generalised dynamic ordinals - universal measures for implicit computational complexity
Arnold Beckmann 
Lecture Notes in Logic, Volume: 27, Pages: 48 - 74
Swansea University Author:
Arnold Beckmann
Abstract
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 [Krajicek1994]. We indicate the role of generalised dynamic ordinal...
| Published in: | Lecture Notes in Logic |
|---|---|
| Published: |
2006
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa13719 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Abstract: |
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 [Krajicek1994]. 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. |
|---|---|
| College: |
Faculty of Science and Engineering |
| Start Page: |
48 |
| End Page: |
74 |