Clote

Feasible Mathematics II

Herausgeber: Clote, Peter; Remmel, Jeffrey B

• Gebundenes Buch

Produktbeschreibung

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.

Produktdetails

• Verlag: Birkhauser Boston / Birkhäuser Boston
• 1995 edition
• Seitenzahl: 447
• Erscheinungstermin: 22. Dezember 1994
• Englisch
• Gewicht: 618g
• ISBN-13: 9780817636753
• ISBN-10: 0817636757
• Artikelnr.: 27468557

Inhaltsangabe

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.