Skip to main content
SpringerLink
Log in
Book cover

Classical and New Paradigms of Computation and their Complexity Hierarchies

Papers of the conference "Foundations of the Formal Sciences III"

  • Conference proceedings
  • © 2004

Overview

Editors:
  1. Benedikt Löwe

    1. Institute for Logic, Language and Computation, Universiteit van Amsterdam, Netherlands

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Boris Piwinger

    1. University of Wien, Austria

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Thoralf Räsch

    1. University of Potsdam, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Focuses on some of the new paradigms of computation, among them Quantum Computing and Infinitary Computation

Part of the book series: Trends in Logic (TREN, volume 23)

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

Access this book

Log in via an institution
eBook USD 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (13 papers)

  1. Front Matter

    Pages i-xiii
    Download chapter PDF

  2. Complexity hierarchies derived from reduction functions

    • Benedikt Löwe
    Pages 1-14

  3. Quantum query algorithms and lower bounds

    • Andris Ambainis
    Pages 15-32

  4. Algebras of minimal rank: overview and recent developments

    • Markus Bläser
    Pages 33-46

  5. Recent developments in iterated forcing theory

    • Jörg Brendle
    Pages 47-60

  6. Classification problems in algebra and topology

    • Riccardo Camerlo
    Pages 61-75

  7. Using easy optimization problems to solve hard ones

    • Lars Engebretsen
    Pages 77-93

  8. On Sacks forcing and the Sacks property

    • Stefan Geschke, Sandra Quickert
    Pages 95-139

  9. Supertask computation

    • Joel David Hamkins
    Pages 141-158

  10. A refinement of Jensen's constructible hierarchy

    • Peter Koepke, Marc van Eijmeren
    Pages 159-169

  11. Effective Hausdorff dimension

    • Elvira Mayordomo Cámara
    Pages 171-186

  12. Axiomatizability of algebras of binary relations

    • Szabolcs Mikulás
    Pages 187-205

  13. Forcing axioms and projective sets of reals

    • Ralf Schindler
    Pages 207-222

  14. Post's and other problems of supertasks of higher type

    • Philip D. Welch
    Pages 223-237

  15. Back Matter

    Pages 239-259
    Download chapter PDF
Back to top

Keywords

About this book

The notion of complexity is an important contribution of logic to theoretical computer science and mathematics. This volume attempts to approach complexity in a holistic way, investigating mathematical properties of complexity hierarchies at the same time as discussing algorithms and computational properties. A main focus of the volume is on some of the new paradigms of computation, among them Quantum Computing and Infinitary Computation. The papers in the volume are tied together by an introductory article describing abstract properties of complexity hierarchies.

This volume will be of great interest to both mathematical logicians and theoretical computer scientists, providing them with new insights into the various views of complexity and thus shedding new light on their own research.

Editors and Affiliations

  • Institute for Logic, Language and Computation, Universiteit van Amsterdam, Netherlands

    Benedikt Löwe

  • University of Wien, Austria

    Boris Piwinger

  • University of Potsdam, Germany

    Thoralf Räsch

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation