Abstract Recursion and Intrinsic Complexity

ISBN-13: 9781108415583 / Angielski / Twarda / 2018 / 250 str.

Yiannis N. Moschovakis

Opis

Presents a new framework for the complexity of algorithms, for all readers interested in the theory of computation.

Recenzje

'… the author presents basic methods, approaches and results of the theory of abstract (first-order) recursion and its relevance to the foundations of the theory of algorithms and computational complexity …' Marat M. Arslanov, Mathematical Reviews Clippings

Spis treści

Introduction; 1. Preliminaries; Part I. Abstract (First Order) Recursion: 2. Recursive (McCarthy) programs; 3. Complexity theory for recursive programs; Part II. Intrinsic Complexity: 4. The homomorphism method; 5. Lower bounds from Presburger primitives; 6. Lower bounds from division with remainder; 7. Lower bounds from division and multiplication; 8. Non-uniform complexity in N; 9. Polynomial nullity (0-testing); References; Symbol index; General index.