Feasible Mathematics

1. Front Matter

   Pages i-viii

   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

    PDF

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.

• Arithmetic
• Finite
• Parity
• algebra
• algorithms
• calculus
• complexity
• computer
• function
• mathematics
• pigeonhole principle
• recursion
• time

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

  Samuel R. Buss

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

  Philip J. Scott

Policies and ethics