Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Marked Items 
Alerts
Order History
Saved Items
All
Favorites
    
Book Chapter Printable view
A Note on Universal Measures for Weak Implicit Computational Complexity

A Note on Universal Measures for Weak Implicit Computational Complexity

Book SeriesLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
ISSN0302-9743 (Print) 1611-3349 (Online)
VolumeVolume 2514/2002
BookLogic for Programming, Artificial Intelligence, and Reasoning
DOI10.1007/3-540-36078-6
Copyright2002
ISBN978-3-540-00010-5
DOI10.1007/3-540-36078-6_4
Pages53-67
Subject CollectionComputer Science
SpringerLink DateTuesday, January 01, 2002
Add to marked items

A Note on Universal Measures for Weak Implicit Computational Complexity

Arnold Beckmann3 Contact Information

(3)  Institute of Algebra and Computational Mathematics, Vienna University of Technology, Wiedner Hauptstr. 8-10/118, A-1040 Vienna, Austria
Abstract
This note is a case study for finding universal measures for weak implicit computational complexity. We will instantiate “universal measures” by “dynamic ordinals”, and “weak implicit computational complexity” by “bounded arithmetic”. Concretely, we will describe the connection between dynamic ordinals and witness oracle Turing machines for bounded arithmetic theories.

Keywords  Bounded arithmetic - Dynamic ordinals - Witness oracle Turing machines - Weak implicit computational complexity

Supported by a Marie Curie Individual Fellowship #HPMF-CT-2000-00803 from the European Commission.

Contact Information Arnold Beckmann
Email: Arnold.Beckmann@logic.at
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.
more options
Find


Export this chapter
Export this chapter as RIS | Text
 
Frequently asked questions | General information on journals and books | Send us your feedback | Impressum | Contact
© Springer. Part of Springer Science+Business Media
Privacy, Disclaimer, Terms and Conditions, © Copyright Information
Remote Address: 38.107.191.107 • Server: mpweb05
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)