Succinct representation and fast access to large amounts of data are challenges of our time. This unique book suggests general approaches of 'complexity of descriptions'. It deals with a variety of concrete topics and bridges between them, while opening new perspectives and providing promising avenues for the 'complexity puzzle'.

1. Introduction ; 2. Morphisms in logic and complexity ; 3. Exponential processes and formal proofs ; 4. Graphs and their visibilities ; 5. Asymptotic growth of infinite visibilities ; 6. Geometric aspects of cut elimination ; 7. Feasibility graphs ; 8. Bounds for finite visibilities ; 9. Some related computational questions ; 10. Mappings and graphs ; 11. Mappings and comparisons ; 12. Adjacency matrices and counting ; 13. Duality and NP-completeness ; 14. Finite automata and regular languages ; 15. Constructions with graphs ; 16. Stronger forms of recursion ; 17. Groups and graphs ; 18. Extended notions of automata ; 19. Geometry of scales in metric spaces ; 20. The Corona decomposition revisited ; Appendix A: Formal proofs: A brief review ; References ; Index

Largely self-contained exposition Attractive to professionals in various areas as well as beginners Opening new perspectives in computational complexity Development of a new geometric language for the study of combinatorial and logical problems in complexity theory

Largely self-contained exposition Attractive to professionals in various areas as well as beginners Opening new perspectives in computational complexity Development of a new geometric language for the study of combinatorial and logical problems in complexity theory