A Note on Universal Measures for Weak Implicit Computational Complexity | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Note on Universal Measures for Weak Implicit Computational Complexity

  • Conference paper
  • First Online:
Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2002)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 2514))

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.

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

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Toshiyasu Arai. Some results on cut-elimination, provable well-orderings, induction and reflection. Ann. Pure Appl. Logic, 95:93–184, 1998.

    Article  MATH  MathSciNet  Google Scholar 

  2. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P question. SIAM J. Comput., 4:431–442, 1975.

    Article  MATH  MathSciNet  Google Scholar 

  3. Arnold Beckmann. Seperating fragments of bounded predicative arithmetic. PhD thesis, Westf. Wilhelms-Univ., Münster, 1996.

    Google Scholar 

  4. Arnold Beckmann. Dynamic ordinal analysis. Arch. Math. Logic, 2001. accepted for publication.

    Google Scholar 

  5. Samuel R. Buss. Bounded arithmetic, volume 3 of Stud. Proof Theory, Lect. Notes. Bibliopolis, Naples, 1986.

    Google Scholar 

  6. Samuel R. Buss. Relating the bounded arithmetic and the polynomial time hierarchies. Ann. Pure Appl. Logic, 75:67–77, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  7. Samuel R. Buss and Jan Krajíček. An application of boolean complexity to separation problems in bounded arithmetic. Proc. London Math. Soc., 69:1–21, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  8. Johan Håstad. Computational Limitations of Small Depth Circuits. MIT Press, Cambridge, MA, 1987.

    Google Scholar 

  9. Jan Johannsen. A note on sharply bounded arithmetic. Arch. Math. Logik Grundlag., 33:159–165, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  10. Jan Krajíček. Fragments of bounded arithmetic and bounded query classes. Trans. Amer. Math. Soc., 338:587–98, 1993.

    Article  MathSciNet  MATH  Google Scholar 

  11. Jan Krajíček. Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press, Heidelberg/New York, 1995.

    MATH  Google Scholar 

  12. Jan Krajíček, Pavel Pudlák, and Gaisi Takeuti. Bounded arithmetic and the polynomial hierarchy. Ann. Pure Appl. Logic, 52:143–153, 1991.

    Article  MathSciNet  MATH  Google Scholar 

  13. Daniel Leivant. Substructural termination proofs and feasibility certification. In Proceedings of the 3rd Workshop on Implicit Computational Complexity (Aarhus), pages 75–91, 2001.

    Google Scholar 

  14. Rohit J. Parikh. Existence and feasibility in arithmetic. J. Symbolic Logic, 36:494–508, 1971.

    Article  MATH  MathSciNet  Google Scholar 

  15. Wolfram Pohlers. Proof Theory. An Introduction. Number 1407 in Lect. Notes Math. Springer, Berlin/Heidelberg/New York, 1989.

    MATH  Google Scholar 

  16. Chris Pollett. Structure and definability in general bounded arithmetic theories. Ann. Pure Appl. Logic, 100:189–245, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  17. Gaisi Takeuti. RSUV isomorphism. In Peter Clote and Jan Krajíček, editors, Arithmetic, proof theory, and computational complexity, Oxford Logic Guides, pages 364–86. Oxford University Press, New York, 1993.

    Google Scholar 

  18. Andrew C. Yao. Separating the polynomial-time hierarchy by oracles. Proc. 26th Ann. IEEE Symp. on Foundations of Computer Science, pages 1–10, 1985.

    Google Scholar 

  19. Domenico Zambella. Notes on polynomially bounded arithmetic. J. Symbolic Logic, 61:942–966, 1996.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Algebra and Computational Mathematics, Vienna University of Technology, Wiedner Hauptstr. 8-10/118, A-1040, Vienna, Austria

    Arnold Beckmann

Authors
  1. Arnold Beckmann
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Abteilung für Theoretische Informatik, Institut für Algebra und Diskrete Mathematik, Wiedner Hauptstr. 8-10, 1040, Wien, Austria

    Matthias Baaz

  2. Department of Computer Science, University of Manchester, Kilburn Building, Oxford Road, Manchester, M13, 9PL, UK

    Andrei Voronkov

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Beckmann, A. (2002). A Note on Universal Measures for Weak Implicit Computational Complexity. In: Baaz, M., Voronkov, A. (eds) Logic for Programming, Artificial Intelligence, and Reasoning. LPAR 2002. Lecture Notes in Computer Science(), vol 2514. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36078-6_4

Download citation

  • DOI: https://doi.org/10.1007/3-540-36078-6_4

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-00010-5

  • Online ISBN: 978-3-540-36078-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation