Abstract recursion and intrinsic complexity / Yiannis N. Moschovakis (University of California, Los Angeles, and University of Athens).
This book presents and applies a framework for studying the complexity of algorithms. It is aimed at logicians, computer scientists, mathematicians and philosophers interested in the theory of computation and its foundations, and it is written at a level suitable for non-specialists. Part I provides...
Saved in:
| Online Access: |
Full Text (via Cambridge) |
|---|---|
| Main Author: | |
| Corporate Author: | |
| Format: | eBook |
| Language: | English |
| Published: |
Cambridge ; New York, NY :
Cambridge University Press,
2019.
|
| Series: | Lecture notes in logic ;
48. |
| Subjects: |
Table of Contents:
- Preliminaries
- Recursive (McCarthy) programs
- Complexity theory for recursive programs
- The homomorphism method
- Lower bounds from Presburger primitives
- Lower bounds from division with remainder
- Lower bounds from division and multiplication
- Non-uniform complexity in N
- Polynomial nullity (0-testing).