Feasible mathematics II

Author(s)

• Clote, Peter
• Remmel, Jeffrey B.

Bibliographic Information

Feasible mathematics II

Peter Clote, Jeffrey B. Remmel, editors

（Progress in computer science and applied logic, v. 13）

Birkhäuser, 1995

• : us
• : gw

Other Title

Feasible mathematics 2

Note

Includes bibliographical references

Description and Table of Contents

Volume

: us ISBN 9780817636753

Description

Perspicuity is part of proof. If the process by means of which I get a result were not surveyable, I might indeed make a note that this number is what comes out - but what fact is this supposed to confirm for me? I don't know 'what is supposed to come out' . . . . 1 -L. Wittgenstein A feasible computation uses small resources on an abstract computa­ tion device, such as a 'lUring machine or boolean circuit. Feasible math­ ematics concerns the study of feasible computations, using combinatorics and logic, as well as the study of feasibly presented mathematical structures such as groups, algebras, and so on. This volume contains contributions to feasible mathematics in three areas: computational complexity theory, proof theory and algebra, with substantial overlap between different fields. In computational complexity theory, the polynomial time hierarchy is characterized without the introduction of runtime bounds by the closure of certain initial functions under safe composition, predicative recursion on notation, and unbounded minimization (S. Bellantoni); an alternative way of looking at NP problems is introduced which focuses on which pa­ rameters of the problem are the cause of its computational complexity and completeness, density and separation/collapse results are given for a struc­ ture theory for parametrized problems (R. Downey and M. Fellows); new characterizations of PTIME and LINEAR SPACE are given using predicative recurrence over all finite tiers of certain stratified free algebras (D.

Table of Contents

Preface.- On the Existence of modulo p Cardinality Functions.- Predicative Recursion and The Polytime Hierarchy.- Are there Hard Examples for Frege Systems?.- On Godel’s Theorems on Lengths of Proofs II: Lower Bounds for Recognizing k Symbol Provability.- Feasibly Categorical Abelian Groups.- First Order Bounded Arithmetic and Small Boolean Circuit Complexity Classes.- Parameterized Computational Feasibility.- On Proving Lower Bounds for Circuit Size.- Effective Properties of Finitely Generated R.E. Algebras.- On Frege and Extended Frege Proof Systems.- Ramified Recurrence and Computational Complexity I: Word Recurrence and Poly-time.- Bounded Arithmetic and Lower Bounds in Boolean Complexity.- Ordinal Bounds for Programs.- Turing Machine Characterizations of Feasible Functionals of All Finite Types.- The Complexity of Feasible Interpretability.

Volume

: gw ISBN 9783764336752

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.

Table of 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.

by "Nielsen BookData"

Details

• NCID: BA24552446
• ISBN:
  • 0817636757
  • 3764336757
• LCCN: 94039297
• Country Code: us
• Title Language Code: eng
• Text Language Code: eng
• Place of Publication: Boston
• Pages/Volumes: viii, 447 p.
• Size: 25 cm
• Classification:
  • LCC : QA267.7
  • DC20 : 511.3
• Subject Headings:
  • LCSH : Computational complexity -- Congresses
  • LCSH : Mathematics -- Congresses
• Parent Bibliography ID:
  • BA07712819