Skip to main content
SpringerLink
Log in
Birkhäuser

Feasible Mathematics

A Mathematical Sciences Institute Workshop, Ithaca, New York, June 1989

  • Book
  • © 1990

Overview

Editors:
  1. Samuel R. Buss

    1. Department of Mathematics, University of California, San Diego, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Philip J. Scott

    1. Department of Mathematics, University of Ottawa, Ottawa, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Progress in Computer Science and Applied Logic (PCS, volume 9)

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 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight 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 (18 chapters)

  1. Front Matter

    Pages i-viii
    Download chapter PDF

  2. Parity and the Pigeonhole Principle

    • M. Ajtai
    Pages 1-24

  3. Computing over the Reals (or an Arbitrary Ring)

    • Lenore Blum
    Pages 25-26

  4. On Model Theory for Intuitionistic Bounded Arithmetic with Applications to Independence Results

    • Samuel R. Buss
    Pages 27-47

  5. Sequential, machine-independent characterizations of the parallel complexity classes AlogTIME, AC k, NC k and NC

    • Peter G. Clote
    Pages 49-69

  6. Characterizations of the Basic Feasible Functionals of Finite Type

    • Stephen A. Cook, Bruce M. Kapron
    Pages 71-96

  7. Functional Interpretations of Feasibly Constructive Arithmetic Abstract

    • Stephen Cook, Alasdair Urquhart
    Pages 97-98

  8. Polynomial-time combinatorial operators are polynomials

    • John N. Crossley, J. B. Remmel
    Pages 99-130

  9. Isols and Kneser Graphs

    • J. C. E. Dekker
    Pages 131-160

  10. Stockmeyer induction

    • Fernando Ferreira
    Pages 161-180

  11. Probabilities of sentences about two linear orderings

    • John Foy, Alan R. Woods
    Pages 181-193

  12. Bounded Linear Logic: A Modular Approach to Polynomial Time Computability

    • Jean-Yves Girard, Andre Scedrov, Philip J. Scott
    Pages 195-209

  13. On Finite Model Theory (Extended Abstract)

    • Yuri Gurevich
    Pages 211-219

  14. Computational Models For Feasible Real Analysis

    • H. James Hoover
    Pages 221-237

  15. Inverting a One-to-One Real Function Is Inherently Sequential

    • Ker-I Ko
    Pages 239-257

  16. On Bounded ∑ 1 1 Polynomial Induction

    • Jan Krajíček, Gaisi Takeuti
    Pages 259-280

  17. Subrecursion and lambda representation over free algebras

    • Daniel Leivant
    Pages 281-291

  18. Complexity-Theoretic Algebra: Vector Space Bases

    • Anil Nerode, J. B. Remmel
    Pages 293-319

  19. When is every recursive linear ordering of type μ recursively isomorphic to a polynomial time linear ordering over the natural numbers in binary form?

    • Jeffrey B. Remmel
    Pages 321-350

  20. Back Matter

    Pages 351-352
    Download chapter PDF
Back to top

Keywords

About this book

A so-called "effective" algorithm may require arbitrarily large finite amounts of time and space resources, and hence may not be practical in the real world. A "feasible" algorithm is one which only requires a limited amount of space and/or time for execution; the general idea is that a feasible algorithm is one which may be practical on today's or at least tomorrow's computers. There is no definitive analogue of Church's thesis giving a mathematical definition of feasibility; however, the most widely studied mathematical model of feasible computability is polynomial-time computability. Feasible Mathematics includes both the study of feasible computation from a mathematical and logical point of view and the reworking of traditional mathematics from the point of view of feasible computation. The diversity of Feasible Mathematics is illustrated by the. contents of this volume which includes papers on weak fragments of arithmetic, on higher type functionals, on bounded linear logic, on sub recursive definitions of complexity classes, on finite model theory, on models of feasible computation for real numbers, on vector spaces and on recursion theory. The vVorkshop on Feasible Mathematics was sponsored by the Mathematical Sciences Institute and was held at Cornell University, June 26-28, 1989.

Editors and Affiliations

  • Department of Mathematics, University of California, San Diego, USA

    Samuel R. Buss

  • Department of Mathematics, University of Ottawa, Ottawa, Canada

    Philip J. Scott

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation