arnold beckmann's pages

Generalised dynamic ordinals - universal measures for implicit computational complexity

File: PDF-File

Author: Arnold Beckmann
Title: Generalised dynamic ordinals - universal measures for implicit computational complexity
Journal: Logic Colloquium '02, Lecture Notes in Logic 27: 48-74, Association for Symbolic Logic, La Jolla, CA, 2006.

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.

websites: Arnold Beckmann 2017-08-28 Valid HTML 4.01! Valid CSS!