No Cover Image

Journal article 495 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...

Full description

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: College of Science
Start Page: 48
End Page: 74