A Graphic Apology for Symmetry and Implicitness

by Alessandra Carbone, Stephen Semmes

Overview

This book brings into focus the contrast between explicit and implicit algorithmic descriptions of objects and presents a new geometric language for the study of combinatorial and logical problems in complexity theory. These themes are considered in a variety of settings, sometimes crossing traditional boundaries. Special emphasis is given to moderate complexity - exponential or polynomial - but objects with multi-exponential complexity also fit in. Among the items under consideration are graphs, formal proofs, languages, automata, groups, circuits, some connections with geometry of metric spaces, and complexity classes (P, NP, co-NP).

Product Details

ISBN-13:	9780198507291
Publisher:	Oxford University Press
Publication date:	08/24/2000
Series:	Oxford Mathematical Monographs
Pages:	520
Product dimensions:	6.10(w) x 9.00(h) x 1.30(d)

About the Author

University of Paris XII

Rice University, Houston

Table of Contents

1. Introduction2. Morphisms in logic and complexity3. Exponential processes and formal proofs4. Graphs and their visibilities5. Asymptotic growth of infinite visibilities6. Geometric aspects of cut elimination7. Feasibility graphs8. Bounds for finite visibilities9. Some related computational questions10. Mappings and graphs11. Mappings and comparisons12. Adjacency matrices and counting13. Duality and NP-completeness14. Finite automata and regular languages15. Constructions with graphs16. Stronger forms of recursion17. Groups and graphs18. Extended notions of automata19. Geometry of scales in metric spaces20. The Corona decomposition revisitedAppendix A: Formal proofs: A brief reviewReferencesIndex

Editorial Reviews

"This monograph addresses the problems associated with describing a mathematical object by an implicit definition, that is, a description using some kind of rule or pattern. Such a definition is less satisfying than an explicit definition, but is often necessary when an explicit definition is not practical or even feasible, such as when an object is very large or complicated. The main theme of this book is that such large or complicated objects often possess an internal symmetry that allows for efficient implicit descriptions using the tools of graph theory. In particular, a kind of oriented graph call a visibility graph is often the best way to express this symmetry." — Mathematical Reviews

From the Publisher