- ホーム
- > 洋書
- > 英文書
- > Computer / General
Full Description
In computational applications, an algorithm may solve a given problem, but be "infeasible" in practice because it requires large time and space resources. A "feasible" algorithm requires a "small" amount of time and/or memory and can be implemented on an abstract computational device such as a Turing machine or a boolean circuit. In investigating feasible algorithms, a wide variety of tools from combinatorics, logic, computational complexity theory and algebra can be employed. The purpose of the workshop on which this volume is based was to carry on the work of the first "Feasible Mathematics" workshop, held in 1989. Both workshops were held at Cornell University and sponsored by the University and Mathematics Sciences Institute. This volume contains contributions to feasible mathematics in three areas: computational complexity theory, proof theory and algebra, with substantial overlap between different fields.
Among the topics covered are: boolean circuit lower bounds, novel characteristics of various boolean and sequential complexity classes, fixed-parameter tractability, higher order feasible functionals, higher order programs related to Plotkin's PCF, combinatorial proofs of feasible length, bounded arithmetic, feasible interpretations, polynomial time categoricity, and algebraic properties of finitely generated recursively enumerable algebras.
Contents
On the existence of modulo p cardinality functions, Miklos Ajtai; predicative recursion and the polytime hierarchy, Stephen Bellantoni; are there hard examples for Frege systems?, Maria Luisa Bonet et al; Goedel's theorems on lengths of proofs II - lower bounds for recognizing k symbol provability, Samuel R. Buss; feasibilty categorical Abelian groups, Douglas Cenzer and Jeffrey Remmel; first order bounded arithmetic and small boolean circiut complexity classes, Peter Clote and Gaisi Takeuti; parametized computational feasibility, Rodney G. Downey and Micheal R. Fellows; on proving lower bounds for circuit size, Mauricio Karchmer; effective properties of finitely generated RE algebras, Bakhadyr Khoussainov and Aail Nerode; on Frege and extended Frege proof systems, Jan Krajicek; ramified recurrence and computational complexity I - word recurrence and poly-time, Daniel Leivant; bounded arithmetic and lower bounds in boolean complexity, Alexander A. Razborov; ordinal bounds for programs, Helmut Schwichtenberg and Stanley S. Wainer; Turing machine characterizations of feasible functionals of all finite types, Anil Seth; the complexity of feasible interpretability, Rineke Verbrugge.
